IMO 1999 Shortlisted Problems with Solutions

Algebra

A2. The numbers \(1\) to \(n^2\) are arranged in the squares of an \(n\times n\) board (1 per square). There are \(n^2(n-1)\) pairs of numbers in the same row or column. For each such pair take the larger number divided by the smaller. Then take the smallest such ratio and call it the minrat of the arrangement. What is the largest possible minrat? S

A3. Each of \(n>1\) girls has a doll with her name on it. Each pair of girls swaps dolls in some order. For which values of \(n\) is it possible for each girl to end up (1) with her own doll, (2) with another girl's doll? S

A4. Show that we cannot partition the positive integers into three non-empty parts, so that if \(a\) and \(b\) belong to different parts, then \(a^2-ab+b^2\) belongs to the third part. S

A6. Given real numbers \(x_1\le x_2\le\cdots\le x_n\) with \(n>2\), carry out the following procedure: (1) arrange the numbers in a circle; (2) delete one of the numbers; (3) if just two numbers are left, take their sum; otherwise replace each number by the sum of it and the number on its right, and go to step (2). Show that the largest sum obtainable is \[ \binom{n-2}{0}x_2+\binom{n-2}{0}x_3+\binom{n-2}{1}x_4+\binom{n-2}{1}x_5+\cdots +\binom{n-2}{\lfloor n/2\rfloor-1}x_n. \] S

Combinatorics

C1. A low path from \((0,0)\) to \((n,n)\) is a sequence of \(2n\) moves, each one up or right, such that \(y\le x\). A step is two consecutive moves, first right and then up. Show that the number of low paths with exactly \(k\) steps is \[ \frac{1}{k}\binom{n-1}{k-1}\binom{n}{k-1}. \] S

C2. A tile is made of five unit squares as shown. Show that if a \(5\times n\) rectangle can be covered with \(n\) tiles, then \(n\) is even. Show also that a \(5\times 2n\) rectangle can be tiled in at least \(2\cdot 3^{\,n-1}\) ways. S

C3. A chameleon repeatedly rests and then catches a fly. The first rest lasts one minute. The rest before catching fly \(2n\) equals the rest before catching fly \(n\). The rest before catching fly \(2n+1\) is one minute longer than before \(2n\). Answer the following questions concerning this process. S

C4. Let \(A\) be any set of \(n\) residues modulo \(n^2\). Show that there exists a set \(B\) of \(n\) residues modulo \(n^2\) such that at least half of all residues modulo \(n^2\) can be written as \(a+b\) with \(a\in A\), \(b\in B\). S

C6. Every integer is colored red, blue, green, or yellow. Let \(m,n\) be distinct odd integers with \(m+n\ne0\). Show that we can find two integers \(a,b\) of the same color such that \(a-b=m\), \(a-b=n\), or \(a-b=m-n\). S

Geometry

G1. Point \(P\) lies inside triangle \(ABC\). Let \(k=\min(PA,PB,PC)\). Show that \[ k+PA+PB+PC \le AB+BC+CA. \] S

G2. Given five points, no three collinear and no four concyclic, show that exactly four of the ten circles through three points contain exactly one of the remaining two points. S

G4. Triangle \(ABC\) contains points \(X,Y,Z\) defined by given ratios and angles. Show that the angles of triangle \(ABC\) are uniquely determined and find the smallest of them. S

G5. Triangle \(ABC\) has inradius \(r\). Certain circles through pairs of vertices orthogonal to the incircle define triangle \(A'B'C'\). Show that the circumradius of \(A'B'C'\) equals \(r/2\). S

G7. Point \(P\) lies inside quadrilateral \(ABCD\) with given angle conditions. Prove that \(AB\cdot PC=BC\cdot PD\) and \(CD\cdot PA=DA\cdot PB\). S

G8. Let \(X\) lie on the circumcircle of triangle \(ABC\). Let \(I',I''\) be the incenters of triangles \(AXC\) and \(BXC\). Show that the circumcircle of triangle \(XI'I''\) passes through a fixed point. S

Number Theory

N2. Prove that every positive rational number can be written as \[ \frac{a^3+b^3}{c^3+d^3} \] for some positive integers \(a,b,c,d\). S

N3. Show that there exist strictly increasing sequences \(\{a_n\}\), \(\{b_n\}\) such that \(a_n(a_n+1)\mid b_n^2+1\) for all \(n\). S

N4. Show that there are infinitely many primes \(p\) for which the decimal period of \(1/p\) is divisible by 3, and determine the maximal possible value of a certain digit sum. S

N5. For any integer \(n\) not divisible by 3 and any \(k\ge n\), show that there exists a multiple of \(n\) whose digit sum equals \(k\). S

N6. For any \(k>0\), find infinitely many integers with digit sum greater than \(k\) forming an arithmetic progression whose difference is not divisible by 10. S