42nd IMO 2001 shortlisted problems and solutions

Algebra

A1.  Let T be the set of all triples (a, b, c) where a, b, c are non-negative integers. Find all real-valued functions f on T such that f(a, b, c) = 0 if any of a, b, c are zero and f(a, b, c) = 1 + 1/6 f(a+1, b-1, c) + 1/6 f(a-1, b+1, c) + 1/6 f(a+1, b, c-1) + 1/6 f(a-1, b, c+1) + 1/6 f(a, b+1, c-1) + 1/6 f(a, b-1, c+1) for a, b, c all positive.

A2.  Show that any infinite sequence a_n of positive numbers satisfies a_n > a_n-12^1/n - 1 for infinitely many n.

A3.  Show that x₁/(1 + x₁²) + x₂/(1 + x₁² + x₂²) + ... + x_n/(1 + x₂² + ... + x_n²) < √n for all real numbers x_i.

A4.  Find all real-valued functions f on the reals such that f(xy) ( f(x) - f(y) ) = (x - y) f(x) f(y) for all x, y.

A5.  Find all positive integers a₀ = 1, a₁, a₂, ... , a_n such that a₀/a₁ + a₁/a₂ + ... + a_n-1/a_n = 99/100 and (a_k+1 - 1)a_k-1 ≥ a_k³ - a_k² for k = 1, 2, ... , n-1.

Combinatorics

C1.  What is the largest number of subsequences of the form n, n+1, n+2 that a sequence of 2001 positive integers can have? For example, the sequence 1, 2, 2, 3, 3, of 5 terms has 4 such subsequences.

C3.  A finite graph is such that there are no subsets of 5 points with all 15 edges and every two triangles have at least one point in common. Show that there are at most two points X such that removing X leaves no triangles.

C4.  Let P be the set of all sets of three integers of the form {n, n+1776, n + 3777} or {n, n+2001, n+3777}. Show that we can write the set {0, 1, 2, 3, ... } as a union of disjoint members of P.

C5.  Find all finite sequences a₀, a₁, a₂, ... , a_n such that a_m equals the number of times that m appears in the sequence.

C6.  Show that there is a set P of (2n)!/(n! (n+1)!) sequences of 2n terms, half 1s and half 0s, such that any sequence of 2n terms, half 1s and half 0s, is either in P or can be derived from a member of P by moving one term. Moving a term means changing a₁, a₂, ... , a_2n to a₁, a₂, ... , a_i-1, a_i+1, ... , a_ja_ia_j+1 ... a_n for some i, j. For example, by moving the initial 0 we can change 0110 to 1010 or 1100, or by moving the first 1 we can change 0110 to 1010 or 0101.

C7.  There are n piles of stones in a line. If a pile contains at least two stones more than the pile on its right, then a stone can be moved to the pile on its right. Initially, all the piles are empty except the leftmost pile which has n stones. If more than one move is possible, then a possible move is chosen arbitrarily. Show that after a finite number of moves, no more moves are possible and that the final configuration is independent of the moves made. Describe the final configuration. For example, we n = 6, one might get successively: 5 1, 4 2, 4 1 1, 3 2 1.

Geometry

G1.  ABC is an acute-angled triangle. A' is the center of the square with two vertices on BC, one on AB and one on AC. Similarly, B' is the center of the square with two vertices on CA, one on AB and one on BC, and C' is the center of the square with two vertices on AB, one on BC and one on CA. Show that AA', BB' and CC' are concurrent.

G3.  ABC is a triangle with centroid G and side lengths a = BC, b = CA, c = AB. Find the point P in the plane which minimises AP.AG + BP.BG + CP.CG and find the minimum in terms of a, b, c.

G4.  P is a point inside the triangle ABC. The feet of the perpendiculars to the sides are D, E, F. Find the point P which maximises PD.PE.PF/(PA.PB.PC). Which triangles give the largest maximum value?

G5.  ABC is an acute-angled triangle. B' is a point on the perpendicular bisector of AC on the opposite side of AC to B such that angle AB'C = 2A. A' and C' are defined similarly (with angle CA'B = 2C, angle BC'A = 2B). The lines AA' and B'C' meet at A". The points B" and C" are defined similarly. Find AA'/A"A' + BB'/B"B' + CC'/C"C'.

G6.  P is a point outside the triangle ABC. The perpendiculars from P meet the lines BC, CA, AB at D, E, F, respectively. The triangles PAF, PBD, PCE all have equal area. Show that their area must equal that of ABC.

G7.  P is a point inside acute-angled the triangle ABC. The perpendiculars from P meet the sides BC, CA, AB at D, E, F, respectively. Show that P is the circumcenter iff each of the triangles AEF, BDF, CDE has perimeter not exceeding that of DEF.

Number theory

N1.  Prove that we cannot find consecutive factorials with first digits 1, 2, ... , 9.

N2.  Find the largest real k such that if a, b, c, d are positive integers such that a + b = c + d, 2ab = cd and a ≥ b, then a/b ≥ k.

N3.  The sequence a_n is defined by a₁= 11¹¹, a₂ = 12¹², a₃ = 13¹³, and a_n+3 = |a_n+2 - a_n+1| + |a_n+1 - a_n|. Find a_n, where n = 14¹⁴.

N4.  Let p > 3 be a prime. Show that there is a positive integer n < p-1 such that n^p-1 - 1 and (n+1)^p-1 - 1 are not divisible by p².

N6.  Do there exist 100 positive integers not exceeding 25000 such that the sum of every pair is distinct? 

Note: problems A6, C2, C8, G2, G8 and N5 were used in the Olympiad and are not shown here.

Solutions

Problem A3

Show that x₁/(1 + x₁²) + x₂/(1 + x₁² + x₂²) + ... + x_n/(1 + x₂² + ... + x_n²) < √n for all real numbers x_i.

 

Solution

Using Cauchy ∑ a_ib_i ≤ √(∑ a_i²) √(&sum b_i²) with a_i = 1, b_i = x_i/(1+x₁²+x₂²+...+x_i²) we have lhs ≤ rhs √(∑ b_i²).

Now use b₁² ≤ x₁²/(1+x₁²) = 1 - 1/(1+x₁²) 

Problem C1

What is the largest number of subsequences of the form n, n+1, n+2 that a sequence of 2001 positive integers can have? For example, the sequence 1, 2, 2, 3, 3, of 5 terms has 4 such subsequences.

 

Solution

Answer: 667³.

We show that 1, ... , 1, 2, ... , 2, 3, ... , 3 (with 667 1s, 667 2s and 667 3s) is maximal. There are several stages. Let the sequence be a₁, a₂, ... , a₂₀₀₁. We show first that there is a maximal sequence with a₁ ≤ a₂ ≤ ... ≤ a₂₀₀₁. For suppose there is a maximal sequence with a_i > a_i+1. Swapping these two terms cannot decrease the number of subsequences n, n+1, n+2. By a series of such swaps we get another maximal sequence with a₁ ≤ a₂ ≤ ... ≤ a₂₀₀₁.

Next we show that there is a maximal sequence with a_i = a_i+1 or a_i+1 + 1 for each i. For suppose a maximal sequence has a_i ≥ a_i+1 + d+1. Then by adding d to a_i and all earlier terms we do not decrease the number of subsequences n, n+1, n+2. So by a series of such changes we can get another maximal sequence with a_i = a_i+1 or a_i+1 + 1 for each i.

Thus there is a maximal sequence with b₀ terms k, followed by b₁ terms k+1, followed by b₂ terms k+2 and so on up to b_h terms k+h. The number of sequences n, n+1, n+2 is evidently N = b₀b₁b₂ + b₁b₂b₃ + b₂b₃b₄ + ... + b_n-2b_n-1b_n. But if n ≥ 2, then changing from b₀, b₁, ... , b_n to b₁, b₂, (b₀ + b₃, b₄, ... b_n increases N by b₀b₂b₄ + b₀b₄b₅ (or leaves it unchanged if n = 3). So we may take n = 2. (Obviously a maximal sequence cannot have n < 2, because then it has no subsequences of the required form.) Only differences matter, so we may take the first term to be 1. Thus there is a maximal sequence 1, ... , 1, 2, ... , 2, 3, ... , 3 with a 1s b 2s and c 3s, where a + b + c = 2001.

Such a sequence obviously has abc subsequences of the required form. But by the arithmetic/geometric mean inequality, abc is maximised by taking a = b = c. 

Problem C5

Find all finite sequences a₀, a₁, a₂, ... , a_n such that a_m equals the number of times that m appears in the sequence.

 

Solution

Answer: (1) 1, 2, 1, 0; (2) 2, 0, 2, 0; (3) 2, 1, 2, 0, 0; (4) N, 2, 1, 0, ... , 0 with N+4 terms, except that a_N = 1.

Note that we cannot have a₀ = 0. Suppose there are k other non-zero terms. The number of 1s is a₁, the number of 2s is a₂ etc, so the number of non-zero terms is a₁ + a₂ + ... + a_n. Hence a₁ + a₂ + ... + a_n = k+1. But if there are k+1 non-zero terms, then k of a₁, a₂, ... , a_n are at least 1. So k-1 of them must be 1, one of them 2 and the rest 0. In particular, none of them are 3 or more (*).

If a₀ is 1 or 2, then no member of the sequence is 3 or more, so a₃ = ... = a_n = 0.

Suppose a₀ = 1. Then a₁ cannot be 1 (or there would be two 1s). It cannot exceed 2, so it must be 2. But the only other term that can be 1 is a₂, so a₂ = 1. We need a 0, so a₃ = 0. There cannot be any further terms, because they would have to be 0s and we have enough already. Thus we have the solution 1, 2, 1, 0.

Suppose a₀ = 2. We know that a₁ cannot exceed 2. Suppose it is 2. Then a₂ is at least 2. Like all the terms, it is at most 2. But if it is 2, then there are three 2s. Contradiction. So a₁ must be 0 or 1. Suppose it is 0. Then a₂ is at least 1 because a₀ is 2. But it cannot be 1, because there are no 1s. So it must be 2. So all remaining terms must be 0. Now there are two 0s, so there must be just one more term, and we have the solution 2, 0, 2, 0.

So suppose a₁ = 1 (and a₀ = 2). Again there are no more 1s. So a₂ must be 2. Hence all remaining terms must be 0. We need two more 0s (to get a₀ correct), so we have the solution 2, 1, 2, 0, 0.

That exhausts the possibilities for a₀ = 1 or 2. So suppose a₀ = N > 2. Hence a_N = 1. So a₁ is at least 1. It cannot be 1 (or there would be two 1s). But by (*) it cannot exceed 2, so it must be 2. Hence, by (*), a₂ must be 1. Since the only term exceeding 2 is a₀ (by (*) ), all of a₃, a₄, ... , a_n except a_N must be 0. We need N zeros, so n = N+3. It is easy to check that a₀ = N (> 2), a₁ = 2, a₂ = 1, a_N = 1 and the rest of a₃, a₄, ... , a_N+3 is indeed a solution.

Problem C6

Show that there is a set P of (2n)!/(n! (n+1)!) sequences of 2n terms, half 1s and half 0s, such that any sequence of 2n terms, half 1s and half 0s, is either in P or can be derived from a member of P by moving one term. Moving a term means changing a₁, a₂, ... , a_2n to a₁, a₂, ... , a_i-1, a_i+1, ... , a_ja_ia_j+1 ... a_n for some i, j. For example, by moving the initial 0 we can change 0110 to 1010 or 1100, or by moving the first 1 we can change 0110 to 1010 or 0101.

 

Solution

Given a sequence x (of length 2n), let f(x) be the sum of the positions of the 1s mod n+1. For example, x = 0110 has 1s in positions 2 and 3, so f(x) = 2 + 3 = 5 = 2 mod 3. Take P_k to be all sequences with f(x) = k. Now suppose a sequence x has 0 in the first position. If we move it to just after the mth 1 to get the sequence y, then we shift each of those 1s one place to the left, so f(y) = f(x) - m mod n+1. So by taking a suitable m (between 1 and n) - or by making no move at all - we can get y into P_k. Similarly, if x has 1 in the first position and we move it to just after the mth 0 to get a sequence y, then if we moved it past h 1s, each of those 1s has its position reduced by 1, but the 1 we are moving has its position increased by m+h, so f(y) = f(x) + m. So we can again get y into P_k. So every sequence either belongs to P_k or can be derived from a member of P_k by a move. But the n+1 sets P_k form a partition the (2n)!/(n! n!) possible sequences, so at least one of them has at most (2n)!/(n! (n+1)!) members. [If it has less then we can add any sequences to bring it up to (2n)!/(n! (n+1)!) members]. 

Problem G1

ABC is an acute-angled triangle. A' is the center of the square with two vertices on BC, one on AB and one on AC. Similarly, B' is the center of the square with two vertices on CA, one on AB and one on BC, and C' is the center of the square with two vertices on AB, one on BC and one on CA. Show that AA', BB' and CC' are concurrent.

 

Solution

Let the ray AA' meet BC at X. Since AX passes through the center of the square, we have VX = q, WX = p, as shown in the diagram. By similar triangles BX/XC = p/q. Hence BX/XC = (BX + p)/(XC + q) = BW/VC = (BV + s)/(CW + s), where s is the side of the square. But BV = s cot B, CW = s cot C, so BX/XC = (cot B + 1)/(cot C + 1). We are now home by Ceva's theorem. 

Problem G3

ABC is a triangle with centroid G and side lengths a = BC, b = CA, c = AB. Find the point P in the plane which minimises AP.AG + BP.BG + CP.CG and find the minimum in terms of a, b, c.

 

Solution

Applying the sine rule to triangle BGL, we have BG/sin BLG = BL/sin BGK. Similarly applying the sine rule to triangle CGL, we have CG/sin CLG = CL/sin CGK. But L is the midpoint of BC and sin BLG = sin CLG, so BG/CG = sin CGK/sin BGK.

We have BK = 2 R sin BGK, where R is the radius of the circle (because if O is its center then ∠BOK = 2 ∠BGK). Similarly, CK = 2 R sin CGK, so CK/BK = BG/CG, and hence BG/CK = CG/BK.

Similarly, AG/BG = sin BGN/sin AGN = sin BGN/sin CGK (opposite angles). Also BC = 2 R sin BKC = 2 R sin BGN (since BGCK is cyclic, so angle BKC = angle BGN). Hence BC/CK = sin BGN/sin CGK = AG/BG, so BG/CK = AG/BC and hence BC : CK : BK = AG : BG : CG.

We now use Ptolemy's theorem on the quadrilateral PBKC: PK.BC <= BP.CK + CP.BK. Hence PK.AG <= BP.BG + CP.CG. Hence (AP + PK)AG <= AP.AG + BP.BG + CP.CG and so finally AK.AG <= AP.AG + BP.BG + CP.CG with equality iff (1) P lies on the circle between B and C (for equality in Ptolemy) and (2) P lies on AK (for equality in the triangle inequality). Thus the unique minimum is when P = G.

Using the cosine formula, we have AB² = AL² + BL² - 2 BL.AL cos ALB, AC² = AL² + CL² - 2 CL.AL cos ALC. Adding, AB² + AC² = 2 AL² + BC²/2, so AG² =(4/9) AL² = (2 AB² + 2 AC² - BC²)/9. Hence AG² + BG² + CG² = (AB² + BC² + CA²)/3. 

Problem G4

P is a point inside the triangle ABC. The feet of the perpendiculars to the sides are D, E, F. Find the point P which maximises PD.PE.PF/(PA.PB.PC). Which triangles give the largest maximum value?

 

Solution

Let n = PD.PE.PF/(PA.PB.PC). We have PF.PE/PA² = sin x sin x' = 1/2 cos(x - x') - 1/2 cos(x + x') = 1/2 cos(x - x') - 1/2 cos A ≤ 1/2 - 1/2 cos A = sin²(A/2), with equality iff P lies on the bisector of angle A. Hence n ≤ sin(A/2) sin(B/2) sin(C/2) with equality iff P is the incenter.

But sin(A/2) sin(B/2) = 1/2 cos(A/2 - B/2) - 1/2 cos(A/2 + B/2) = 1/2 cos(A/2 - B/2) - 1/2 sin C/2. So sin(A/2) sin(B/2) sin(C/2) can only be maximal if A/2 = B/2. Hence it can only be maximal if A = B = C. So the unique maximum is if the triangle is equilateral.

Problem G5

ABC is an acute-angled triangle. B' is a point on the perpendicular bisector of AC on the opposite side of AC to B such that angle AB'C = 2A. A' and C' are defined similarly (with ∠CA'B = 2∠C, ∠BC'A = 2∠B). The lines AA' and B'C' meet at A". The points B" and C" are defined similarly. Find AA'/A"A' + BB'/B"B' + CC'/C"C'.

 

Solution

Answer: 4.

Note that ∠B' is not twice ∠B, but twice ∠A, so ∠BAB' = ∠CBC' = ∠ACA' = 90^o. Also ∠B'AC = 90^o + (90^o - ∠B) < 180^o. Note also that the reason for ABC being acute-angled is to ensure that ∠AB'C < 180^o (so that B' does indeed lie on the opposite side of AC to B). Thus AB'CA'BC' is convex.

Let the circle center B' through A and C meet the circle center A' radius B and C at O. Then ∠AOC = 180^o - 1/2 ∠AB'C = 180^o - ∠A. Similarly, ∠COB = 180^o - ∠C. Hence ∠AOB = 360^o - ∠AOC - ∠COB = ∠A + ∠C = 180^o - ∠B. Hence O also lies on the circle center C' through A and B. Now since the circles center A' and B' meet at O and C, the points O and C are reflections in A'B'. Similarly for O and A, and O and B.

AA'/A"A' = 1 + AA"/A'A" = 1 + area AB'C'/area A'B'C'. Hence AA'/A"A' + BB'/B"B' + CC'/C"C' = 3 + (area AB'C' + area BC'A' + area CA'B')/area A'B'C' = 3 + (area OB'C' + area OC'A' + area OA'B')/area A'B'C' = 4. 

Problem G6

P is a point outside the triangle ABC. The perpendiculars from P meet the lines BC, CA, AB at D, E, F, respectively. The triangles PAF, PBD, PCE all have equal area. Show that their area must equal that of ABC.

 

Solution

In principle, there are two possible configurations: (1) P can lie between the two rays BA and BC (on the opposite side of AC to B), or similarly between the rays AB and AC or between the rays CA and CB; or (2) P can lie between the rays AB and CB (on the infinite side, opposite to A and C), or the two similar arrangemetns. But the second case implies that one of the triangles PAF, PBD, PCE is a proper subset of another, so it is not possible. Thus, without loss of generality, we have the configuration shown below. Take area PAF = area PBD = area PCE = x. Also put area APE = u, area ABE = v and area CBE = w.

BD/DC = area ADB/area ADC = area PDB/area PDC. So (x - u - v)/(x - v + w) = x/(2x + w). Hence x² - x(2u + v) - uw - vw = 0 (*). Similarly, CE/EA = area CBE/area CBA = area CPE/area EPA, so w/u = x/v. Substituting in (*) gives x² - x(2u + ux/w) - ux - uw = 0, or x²(w - u) = uw(3x + w). Similarly, AF/FB = area AFP/area FPB = area AFC/area FCB, so x/(x + u + v) = (2x + v)/(2x + u + v + w) (**). Again, eliminating v, we get x = w(w² - uw - u²)/(u² + 2uw). Now eliminating x, we get (w - u)(w + u)(w³ - 3uw² - 4u²w - u³) = 0. Obviously we cannot have w + u = 0 (for that means area ABC = 0, but then ABC is not a triangle). If w - u = 0, then v = x, so (**) gives x/(2x + u) = 3x/(3x + 2u), so 3x + u = 0, so x = 0, which is impossible. So we must have w³ = 3uw² + 4u²2 + u³ = u(3w + u)(w + u).

Hence x = (w³ - uw(u+w) )/(u² + 2uw) = (u+w) ( u(3w+u) - uw)/(u² + 2uw) = u+w, which is the required result. 

Problem G7

P is a point inside acute-angled the triangle ABC. The perpendiculars from P meet the sides BC, CA, AB at D, E, F, respectively. Show that P is the circumcenter iff each of the triangles AEF, BDF, CDE has perimeter not exceeding that of DEF.

 

Solution

One way is obvious: if P is the circumcenter, then D, E, F are the midpoints of the sides and so AEF, BDF, CDE, DEF all have the same area. So assume area AEF ≤ area DEF, area BDF ≤ area DEF and area CDE ≤ area DEF, but P is not the circumcenter. We will obtain a contradiction.

Let the angles in the triangles be as shown in the diagram (there was not room to mark y" = angle DEC.) Take B' so that BDB'F is a parallelogram. Then area BDF = area B'DF, so E cannot lie inside the triangle B'DF (except possibly at B' itself), because then we would have area DEF < area BDF. Suppose E = B'. Then EF is parallel to BC, and DE is parallel to AB. Hence PD is perpendicular to EF, and PF is perpendicular to DE. Hence P is the orthocenter of DEF and so PE is perpendicular to DF, so DF is parallel to AC. Hence BDEF and AFDE are parallelograms, so BF = DE = AF, in other words F is the midpoint of AB. Similarly, D and E are also midpoints. Hence P is the circumcenter. Contradiction.

So we may assume that E is not any point of B'DF. Hence either x' < y or z" < y. Similarly, y' < z or x" < z, and z' < x or y" < x. Without loss of generality we may assume y' < z (there is symmetry between y' and y"). So looking at triangle AEF, z" > y. Hence x' < y. So looking at CDE, y" > x. Hence z' < x. Looking at BDF, x" > z. So x' < y < z", y' < z < x", and z' < x < y".

Now AEPF is cyclic, so ∠AEF = ∠APF, so AP = PF/cos y'. Similarly, BDPF is cyclic, so ∠BDF = ∠BPF, so BP= PF/cos x" > PF/cos y' = AP. Similarly, CP > BP and AP > CP. Contradiction.

 

Problem N1

Prove that we cannot find consecutive factorials with first digits 1, 2, ... , 9.

 

Solution

We can write any integer n in scientific notation as n = n x 10^k, where 1 ≤ n < 10 is a real number and k is a positive integer. For example, 356 = 3.56 x 10². Suppose that (N+i)! has first digit i for i = 1, 2, ... , 9. Then (N+i)! is a real number between i and i+1. So for i = 2, ... , 9, we have that N+i is a real number such that 1 < N+i = (N+i)!/(N+i-1)! < (i+1)/(i-1). So certainly N+i < 3 and hence N+i < N+i+1. Thus we must have 1 < N+2 < N+3 < ... < N+9 < 5/4.

But ab = a b unless a b > 10, in which case ab = (a b)/10. So in any case ab ≤ a b. Hence (N+4)! = (N+1)! N+2 N+3 N+4 < 2 (5/4) (5/4) (5/4) = 250/64 < 4. Contradiction (because it is supposed to have first digit 4). 

Problem N2

Find the largest real k such that if a, b, c, d are positive integers such that a + b = c + d, 2ab = cd and a ≥ b, then a/b ≥ k.

 

Solution

Answer: k = 3 + 2√2.

A few examples of such a, b, c, d are:

2 + 12 = 6 + 8, 2.2.12 = 6.8, so a/b = 6
2 + 15 = 5 + 12, 2.2.15 = 5.12, so a/b = 7.5
3 + 20 = 8 + 15, 2.3.20 = 8.15, so a/b = 6.67

We have (a+b)² - 8ab = (c+d)² - 4cd, so (a/b)² - 6(a/b) + 1 = ((c-d)/b)² ≥ 0. The plot of x² - 6x + 1 is shown below. It has zeros at x = 3 - 2√2 < 1 and 3 + 2√2 = 5.83. So since a/b ≥ 1, we must have a/b > 3 + 2√2.

The harder part is showing that we can get as close as we like to 3 + 2√2 and hence that k = 3 + 2√2. The idea is to show that we can make (c-d)/b as small as we like.

Note first that (a+b)² - 4ab = (c+d)² - 2cd, so (a-b)² = c² + d². In other words, a-b, c, d is a Pythagorean triple. It is well-known that r² + s², r² - s², 2rs are such triples for any integers r, s. Then we have a+b = c+d = r² + 2rs - s². Hence a = r² + rs, b = rs - s². It is now easy to check that a = r² + rs, b = rs - s², c = r² - s², d = 2rs satisfy a + b = c + d, 2ab = cd.

Suppose we specialise to c - d = 1 (then if we could get arbitrarily large b we would be home). That requires r² - s² - 2rs = 1, or (r - s)² - 2s² = 1. We recognise that as a Pell equation. It has a solution r - s = 3, s = 2. But if (R, S) is a solution to x² - 2y² = 1, so is (3R+4S, 2R+3S). So we can get arbitrarily large r - s and s such that c - d = 1. Then b = rs - s² = (r - s)s, which can therefore be made arbitrarily large as required.

For example, r - s = 3, s = 2, gives r = 5, so a = 35, b = 6, c = 21, d = 20. Then a/b = 5.8333. The next solution is r - s = 17, s = 12, so r = 29, so a = 1189, b = 204, c = 697, d = 696 and a/b = 5.828431 (cf 3 + 2√2 = 5.828427).

Problem N3

The sequence a_n is defined by a₁= 11¹¹, a₂ = 12¹², a₃ = 13¹³, and a_n+3 = |a_n+2 - a_n+1| + |a_n+1 - a_n|. Find a_n, where n = 14¹⁴.

 

Solution

Answer: 1.

This looks so horrendous that appearances must be deceiving. Suppose we take smaller initial values to try to get a sense of what is going on.

term 1  3  7  6  5  2  4  5  3  3  2  1  2  2  1  1  1  0  1  2  2  1
diff  2  4  1  1  3  2  1  2  0  1  1  1  0  1  0  0  1  1  1  0  1

We now have a repetition of 1, 2, 2, so the sequence has period 7 and just repeats the cycle 1, 2, 2, 1, 1, 1, 0. Take another example, starting with 3, 21, 25. After a longer initial lead-in we again get a sequence with period 7:

3  21  25  22   7  18  26  19  15  11   8   7   4   4   3   1   3   4   3   2   2   1
 18   4   3  15  11   8   7   4   4   3   1   3   0   1   2   2   1   1   1   0

Finally, we try something less random. It is evidently periodic right from the start.

k    k    k   0   k  2k  2k   k   k   k
  0   0   k   k   k   0   k   0   0

The last case shows that the terms do not necessarily become small, but we hope that they do unless the starting values are special.

Note that 100, 0, 100 is followed by 200, so terms can go up. Studying the examples above, the differences look easier to deal with. The examples suggest that if three successive differences are a, b, c, then the next is |c - a|. If three successive differences are a, b, c, then the corresponding terms must be A, B, C, a + b. The next term will be b + c. So the next difference will be |b+c - (a+b)| = |c - a|. That is certainly less than max(a, c) and hence less than max(a, b, c). In particular, the differences are certainly bounded.

Suppose max(a, b, c) = M > 1. The following differences are all <= M, so moving forward one or two places in the sequence if necessary, we can assume that a = M. Thus the differences are M, b, c, d, e, f, g, ... . We claim that max(e, f, g) < M unless b and c are both 0 or M. If not, then max(b, c, d) = max(c, d, e) = max(d, e, f) = max(e, f, g) = M (because once the max dips down it can never get back up). But d = |M - c| = M - c. So at least one of b, c, M-c must be M.

Suppose b = M. Then e = |M - c - M| = c. But max(c, d, e) = max(c, M-c, c) = M, so c = 0 or M. Thus both b and c are 0 or M. Contradiction.

Suppose c = M. Then d = 0, e = |0 - b| = b, f = |b - M| = M - b, so max(d, e, f) = max(b, M-b) = M, so b = 0 or M. Thus both b and c are 0 or M. Contradiction.

Finally, suppose c = 0. Then d = M, e = M-b, f = M-b, g = b, so max(e, f, g) = max(M-b, b) = M, so b = 0 or M. Contradiction.

Now suppose three successive differences are all 0 or M. Then two successive terms (not differences) are 0, M or 2M. Working backwards we find that all terms must be multiples of M:

...  A   B   C
... z   a   b 

a and b are multiples of M, so C = a+b must be a multiple of M. But B = C±b, so B must be a multiple of M. But B = a+z, so z must be a multiple of M. Also A = B±a, so A must be a multiple of M, and so on. However, for the particular values we have been given, the greatest common divisor of the first two terms is 1, so M must be 1. Contradiction.

Thus we have established that if three successive differences have maximum M > 1, then we can find three successive terms starting at most 6 places further on which have a strictly smaller maximum. Continuing in this way, we find that the three successive differences starting at most 6M places further on have maximum 1 or less. In other words every difference is 0 or 1 once one gets sufficiently far. Hence all terms a_n with n > 6M are 0, 1 or 2. Since N = 14¹⁴ is obviously much larger than M for the first few differences, we conclude that a_N = 0, 1 or 2.

We now work mod 2. Note that a₁, a₂, a₃ = 1, 0, 1 mod 2. We can now calculate successively:

n 1  2  3  4  5  6  7     8  9 10
an 1  0  1  0  0  1  1     1  0  1

Since a₈, a₉, a₁₀ are the same as a_1,, a₂, a₃ the sequence must be periodic with period 7. But N = 14¹⁴ = 0 mod 7, so a_N = a₇ = 1 mod 2. Hence a_N = 1.

Problem N4

Let p > 3 be a prime. Show that there is a positive integer n < p-1 such that n^p-1 - 1 and (n+1)^p-1 - 1 are not divisible by p².

 

Solution

By the binomial theorem we have (p - a)^p-1 - a^p-1 = (p-1) p a^p-1 mod p². For 0 < a < p, (p-1) p a = p mod p², so (p - a)^p-1 and a^p-1 are unequal mod p². Hence at most one of them is 0 mod p². In particular, since 1² = 1 mod p², we must have (p-1)^p-1 ≠ 1 mod p². Also, at least (p-3)/2 of 2, 3, ... , p-2 must have p-1th powers ≠ 1 mod p². So either one of the pairs (2, 3), (4, 5), ... , (p-3, p-2) has both members with p-1th powers ≠ 1 mod p², in which case we are done, or exactly one member of each pair has p-1th power ≠ 1 mod p².

Now if p-2 has p-1th power ≠ 1 mod p² then we are done (because of p-1). If not, then p-3 has p-1th power ≠ 1 mod p². Now suppose (p-4)^p-1 = 1 mod p². Then (expanding) 1 = 4^p-1 - (p-1)p 4^p-2 = 4^p-1 + p 4^p-2 mod p² (*). But (p-2)^p-1 = 1 mod p², so (expanding) 1 = 2^p-1 + p 2^p-2 mod p². Squaring, 1 = 4^p-1 + p 4^p-1 mod p². Subtracting from (*), 0 = p(4^p-1 - 4^p-2) = 3 p 4^p-2 mod p², but that is clearly false. So we must have (p-4)^p-1 ≠ 1 mod p² and we are home (with p-4 and p-3). 

Comment. This is a weak result. There are relatively few a for which a^p-1 = 1 mod p².

Problem N6

Do there exist 100 positive integers not exceeding 25000 such that the sum of every pair is distinct?

 

Solution

Answer: yes.

We show how to find p integers <= 2p² for any prime p. Since 2.101² < 25000, that is sufficient.

Let n denote the residue of n² mod p. We claim that the integers 2p + 1, 4p + 2, 6p + 3, ... , 2p p + p work. If (2ap + a) + (2bp + b) = (2cp + c) + (2dp + d), then 2(a + b)p + (a + b) = 2(c + d)p + (c + d) and hence a + b = c + d and a + b = c + d (since n < p). Hence a + b = c + d mod p and a² + b² = c² + d² mod p. So a = c + d - b mod p. Substituting in the next equation, (c + d - b)² + b² = c² + d² mod p, so 2(b² - bc - bd - cd) = 0 mod p, or 2(b - c)(b - d) = 0 mod p. Hence b = c or d. So the sum of every pair is distinct.

Read more »

Posted in: IMO shortlist

41st IMO 2000 shortlisted problems and solutions

Algebra

A2.  a, b, c are positive integers such that b > 2a, c > 2b. Show that there is a real k such that the fractional parts of ka, kb, kc all exceed 1/3 and do not exceed 2/3.

A3.  Find all pairs of real-valued functions f, g on the reals such that f(x + g(y) ) = x f(y) - y f(x) + g(x) for all real x, y.

A4.  The function f on the non-negative integers takes non-negative integer values and satisfies f(4n) = f(2n) + f(n), f(4n+2) = f(4n) + 1, f(2n+1) = f(2n) + 1 for all n. Show that the number of non-negative integers n such that f(4n) = f(3n) and n < 2^m is f(2^m+1).

A6.  0 = a₀ < a₁ < a₂ < ... and 0 = b₀ < b₁ < b₂ < ... are sequences of real numbers such that: (1) if a_i + a_j + a_k = a_r + a_s + a_t, then (i, j, k) is a permutation of (r, s, t); and (2) a positive real x can be represented as x = a_j - a_i iff it can be represented as b_m - b_n. Prove that a_k = b_k for all k.

A7.  A polynomial p(x) of degree 2000 with distinct real coefficients satisfies condition n if (1) p(n) = 0 and (2) if q(x) is obtained from p(x) by permuting its coefficients, then either q(n) = 0, or we can obtain a polynomial r(x) by transposing two coefficients of q(x) such that r(n) = 0. Find all integers n for which there is a polynomial satisfying condition n.

Combinatorics

C2.  A piece is made of 12 unit cubes. It looks like a staircase of 3 steps, each of width 2. Thus the bottom layer is 2 x 3, the second layer is 2 x 2 and the top layer is 1 x 2. For which n can we make an n x n x n cube with such pieces?

C3.  n > 3. S = {P₁, ... , P_n} is a set of n points in the plane, no three collinear and no four concyclic. Let a_i be the number of circles through three points of S which have P_i as an interior point. Let m(S) = a₁ + ... + a_n. Show that the points of S are the vertices of a convex polygon iff m(S) = f(n), where f(n) is a value that depends only on n.

C4.  Find the smallest number of pawns that can be placed on an n x n board such that no row or column contains k adjacent unoccupied squares. Assume that n/2 < k ≤ 2n/3.

C5.  n rectangles are drawn in the plane. Each rectangle has parallel sides and the sides of distinct rectangles lie on distinct lines. The rectangles divide the plane into a number of regions. For each region R let v(R) be the number of vertices. Take the sum ∑ v(R) over the regions which have one or more vertices of the rectangles in their boundary. Show that this sum is less than 40n.

For example, for the two rectangles illustrated the sum is 28 < 80. Note that the unbounded outer region has 12 vertices, and we do not count the central region because it does not contain any vertices of the two rectangles.

C6.  a and b are positive coprime integers. A subset S of the non-negative integers is called admissible if 0 belongs to S and whenever k belongs to S, so do k + a and k + b. Find f(a, b), the number of admissible sets.

Geometry

G1.  Two circles C and C' meet at X and Y. Find four points such that if a circle touches C and C' at P and Q and meets the line XY at R and S, then each of the lines PR, PS, QR, QS passes through one of the four points.

G3.  ABC is an acute-angled triangle with orthocenter H and circumcenter O. Show that there are points D, E, F on BC, CA, AB respectively such that OD + DH = OE + EH = OF + FH and AD, BE, CF are concurrent.

G4.  Show that a convex n-gon can be inscribed in a circle iff there is a pair of real numbers a_i, b_i associated with each vertex P_i such that the distance between each pair of vertices P_iP_j with i < j is a_ib_j - a_jb_i.

G5.  ABC is an acute angled triangle. The tangent at A to the circumcircle meets the tangent at C at the point B'. BB' meets AC at E, and N is the midpoint of BE. Similarly, the tangent at B meets the tangent at C at the point A'. AA' meets BC at D, and M is the midpoint of AD. Show that ∠ABM = ∠BAN. If AB = 1, find BC and AC for the triangles which maximise ∠ABM.

G6.  ABCD is a convex quadrilateral. The perpendicular bisectors of AB and CD meet at Y. X is a point inside ABCD such that ∠ADX = ∠BCX < 90^o and ∠DAX = ∠CBX < 90^o. Show that ∠AYB = 2 ∠ADX.

G7.  Ten gangsters are standing in a field. The distance between each pair of gangsters is different. When the clock strikes, each gangster shoots the nearest gangster dead. What is the largest number of gangsters that can survive?

Number theory

N1.  Find all positive integers n > 1 such that if a and b are relatively prime then a = b mod n iff ab = 1 mod n.

N2.  Find all positive integers n such that the number of positive divisors of n is (4n)^1/3.

N4.  Find all positive integers a, m, n such that a^m + 1 divides (a + 1)ⁿ.

N5.  Show that for infinitely many positive integers n, we can find a triangle with integral sides whose semiperimeter divided by its inradius is n.

N6.  Show that all but finitely many positive integers can be represented as a sum of distinct squares. 

Note: problems A1, A5, C1, G2, G8 and N3 were used in the Olympiad and are not shown here.

Solutions

Problem A2

a, b, c are positive integers such that b > 2a, c > 2b. Show that there is a real k such that the fractional parts of ka, kb, kc all exceed 1/3 and do not exceed 2/3.

 

Solution

Let I_n denote the interval ( (n + 1/3)/a, (n + 2/3)/a ]. Similarly, let J_n denote the interval ( (n + 1/3)/b, (n + 2/3)/b ], and K_n denote the interval ( (n + 1/3)/c, (n + 2/3)/c ]. We wish to show that there is some real value k which belongs to intervals of all three types, for k ∈ I_n is equivalent to (n + 1/3) < ak ≤ (n + 2/3) and hence to the fractional part of ak being > 1/3 and ≤ 2/3. Similarly for the other intervals.

The intervals K_n are spaced a distance 2/(3c) < 1/(3b) apart. The intervals J_n all have width 1/(3b), so every J_n must intersect some K_m. We claim that we can find a J_n which is contained in some I_s. It follows that a common point of J_n and K_m also belongs to I_s and we are done. It remains to prove the claim.

J_n ⊆ I_s is equivalent to (s + 1/3)/a ≤ (n + 1/3)/b and (n + 2/3)/b ≤ (s + 2/3)/a, or (3s+1)/(3n+1) ≤ a/b ≤ (3s+2)/(3n+2). Now a/b lies in the interval (0, 1/2). We show that for any real number h in (0, 1/2) we can find s, n such that (3s+1)/(3n+1) ≤ h ≤ (3s+2)/(3n+2).

For if h ≤ 1/4, then we can take the smallest positive integer N such that 1/(3.2^N + 1) < h. Then 2/(3.2^N + 2) = 1/(3.2^N-1 + 1) ≥ h. [Note that if N = 1, this is still true since 1/3 > 1/4 ≥ h.]. Hence h belongs to the interval [1/(3.2^N + 1), 2/(3.2^N + 2) ) and we can put s = 0, n = 2^N.

For N = 0, 1, 2, 3, ... we have (3.2^N - 2)/(3.2^N+1- 2) = 1/4, 2/5, 5/11, ... . The sequence obviously tends to 1/2. So for any h satsifying 1/4 < h < 1/2 take the smallest non-negative integer N such that (3.2^N - 2)/(3.2^N+1 - 2) ≤ h. So h < (3.2^N+1 - 2)/(3.2^N+2 - 2) = (3.2^N - 1)/(3.2^N+1 - 1) = (3s+2)/(3n+2), with s = (2^N - 1), n = (2^N+1 - 1). Also (3.2^N - 2)/(3.2^N+1 - 2) = (3s+1)/(3n+1), so (3s+1)/(3n+1) ≤ h < (3s+2)/(3n+2), as required. 

Note that we do not require a, b, c to be integral.

Problem A3

Find all pairs of real-valued functions f, g on the reals such that f(x + g(y) ) = x f(y) - y f(x) + g(x) for all real x, y.

 

Solution

Answer: f(x) = t(x-t)/(t+1), g(x) = t(x-t) for any real t not equal to -1.

We show first that g(h) = 0 for some h. If f(0) = 0, then putting y = 0 the equation gives f(x + g(0) ) = g(x). Putting h = -g(0) we get g(h) = f(0) = 0.

Suppose f(0) = b, which is non-zero. Let g(0) = a. Putting x = 0, the equation gives f( g(y) ) = a - by. Hence g is injective and f is surjective. Replacing x by g(x) in the equation we get: f( g(x) + g(y) ) = g(x) f(y) - y f( g(x) ) + g( g(x) ). Similarly, replacing x by g(y) and y by x in the equation, we get: f( g(x) + g(y) ) = g(y) f(x) - x f( g(y) ) + g( g(y) ). Equating, g(x) f(y) - y(a - bx) + g( g(x) ) = g(y) f(x) - x(a - by) + g( g(y) ) (*).

f is surjective, so there is c such that f(c) = 0. Putting y = c in (*), we get - ac + g( g(x) ) = g(c) f(x) - ax + g( g(c) ). Putting g(c) = k and g( g(c) ) + ac = d, this becomes g( g(x) ) = k f(x) - ax + d. Substituting back into (*) we get g(x) f(y) - ay + k f(x) - ax + d = g(y) f(x) - ax + k f(y) - ay + d or g(x) f(y) + k f(x) = g(y) f(x) + k f(y). Putting y = 0, g(x) = (a - k)/b f(x) + k. We assumed that f(0) was non-zero, so c is non-zero. So, since g is injective a = g(0) is not equal to k = g(c). Hence g(x) is surjective. So there must be some h such that g(h) = 0.

Now put h into the given equation. We get f(x) = x f(h) - h f(x) + g(x), so g(x) = (h+1) f(x) - f(h) x (**). Substituting back into the given equation, we get f(x + g(y) ) = (h+1 - y) f(x) + ( f(y) - f(h) ) x. Putting y = h+1, f(x + g(h+1) ) = ( f(h+1) - f(h) ) x. Writing n = g(h+1), m = f(h+1) - f(h), we get f(x + n) = mx. So f(x) is linear. So (**) shows that g(x) is also linear.

So put f(x) = rx + s, g(x) = tx + u. The original equation now gives rx + r(ty + u) + s = x(ry + s) - y(rx + s) + tx + u, or rx + rty + (ru+s) = (s+t)x - sy + u. Equating coefficients:
r = s + t   (1)
rt = -s     (2)
ru+s = u   (3).
We cannot have t = -1, for then r = s from (2), and so t = 0 from (1), contradiction. Substituting (2) into (1) we get r = t/(t+1). Then (2) gives s = -t²/(t+1). Then (3) gives u(1-r) = s, so u = -t².

Finally, we check that this solution works. g(y) = t(y-t), so f(x + g(y) ) = t(x + ty - t² - t)/(t+1). Whilst x f(y) - y f(x) + g(x) = (y - x)t²/(t+1) + t(x-t) = t( tx + x - t² - t + ty - tx)/(t+1) = f(x + g(y) ). 

Problem A4

The function f on the non-negative integers takes non-negative integer values and satisfies f(4n) = f(2n) + f(n), f(4n+2) = f(4n) + 1, f(2n+1) = f(2n) + 1 for all n. Show that the number of non-negative integers n such that f(4n) = f(3n) and n < 2^m is f(2^m+1).

 

Solution

f(4.0) = f(2.0) + f(0), so f(0) = 0. Hence f(1) = f(2.0+1) = f(0) + 1 = 1, f(2) = f(4.0+2) = f(0) + 1 = 1. Similarly, f(3) = f(2.1+1) = f(2) + 1 = 2. Calculating a few more terms, in a similar way, we get:

n 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21
f(n) 0   1   1   2   2   3   3   4   3   4   4   5   5   6   6   7   5   6   6   7   7   8

The pattern is not obvious.

However, we may notice f(4n) = f(2n) + f(n). That implies that f(2^k+2) = f(2^k+1) + f(2^k). So if we put f(2^k) = f_k, then f_k is just the kth Fibonacci number. A little further study may then suggest that each f(n) is a sum of Fibonnacci numbers. In fact, if n = b_k...b₀ in binary, then f(n) = b_kf_k+1 + ... + b₀f₁.

To prove this, we just have to verify the equalities in the question. Suppose n = b_k ... b₀. Then f(n) + f(2n) = (b_kf_k+1 + ... + b₀f₁) + (b_kf_k+2 + ... + b₀f₂) = b_kf_k+3 ... b₀f₃ = f(4n), which establishes the first equality. The second and third are obvious.

We now claim that f(3n) = f(4n) iff no two 1s appear in adjacent positions in the binary expansion of n.

Granting the claim, it remains to show that there are f_m+2 integers < 2^m with no adjacent 1s. We prove this by induction on m. For m = 1, we have 0 and 1, and f₃ = 2. For m = 2, the integers are 0, 1, 3 = 10₂, and f₄ = 3. Suppose it is true for integers < m. Take n < 2^m. Let the binary expansion of n be b_m-1 ... b₀. Then n < 2^m-1 iff b_m-1 = 0. In this case there are f_m+1 possible numbers (by induction). If 2^m-1 ≤ n < 2^m, then b_m-1 = 1, so b_m-2 = 0. There are then f_m possibilities for the remaining digits (by induction). So in total there are f_m + f_m+1 = f_m+2 possible numbers.

It remains to prove the claim. Suppose there are no adjacent 1s. Then 3n = 2n + n, and there are no carries when this is computed in binary. So if f(n) = b_kf_k+1 + ... + b₀f₁, then f(3n) = b_k(f_k+1 + f_k+2) + ... + b₀(f₁ + f₂) = b_kf_k+3 + ... + b₀f₃ = f(4n).

The reverse implication is harder. Let S_m be the statement that for 0 < n < 2^m we have f(3n) ≤ f(4n) with equality only if the 1s are isolated. For m = 1 we must have n = 1. We have f(3) = f(4) = 2, so S₁ is true. So assume S_m is true. Let n = 2^m + k with 0 ≤ k < 2^m. Then f(4n) = f(2^m+2 + 4k) = f_m+3 + f(4k).

There are three cases to consider.

Case 1. 0 < k < 2^m/2. Then 3k < 2^m, so the binary representations of 3.2^m = 2^m+1 + 2^m and 3k do not overlap. So f(3n) = f(2^m+1 + 2^m + 3k) = f_m+2 + f_m+1 + f(3k) = f_m+3 + f(3k) ≤ f_m+3 + f(4k) (by induction) = f(4n) and we have equality only if the 1s are isolated (since k < 2^m, if the 1s are isolated in k, then the 1s are also isolated in n = 2^m + k).

Case 2. 2^m/3 < k < 2^m+1/3. Then 3k = 2^m + h with h < 2^m, so f(3k) = f_m+1 + f(h). But 3n = 2(^m+1 + 2^m) + 3k = 2^m+2 + h, so f(3n) = f_m+3 + f(h) = f_m+3 + f(3k) - f_m+1 = f_m+2 f(3k) ≤ f_m+2 + f(4k) (by induction) < f_m+3 + f(3k). We cannot have equality in this case.

Case 3. 2^m+1/3 < k < 2^m. So 3k = 2^m+1 + h with h < 2^m, so f(3k) = f_m+2 + f(h). We have 3n = (2^m+1 + 2^m) + 2^m+1 + h = 2^m+2 + 2^m + h, so f(3n) = f_m+3 + f_m+1 + f(h) = f_m+3 - f_m+2 + f_m+1 + f(3k) < f_m+3 + f(3k) ≤ f_m+3 + f(4k) = f(4n). We cannot have equality in this case. That completes the proof of the claim.

Problem A6

a₀ < a₁ < a₂ < ... and 0 = b₀ < b₁ < b₂ < ... are sequences of real numbers such that: (1) if a_i + a_j + a_k = a_r + a_s + a_t, then (i, j, k) is a permutation of (r, s, t); and (2) a positive real x can be represented as x = a_j - a_i iff it can be represented as b_m - b_n. Prove that a_k = b_k for all k.

 

Solution

Notice first that x > 0 can have at most one representation as a_j - a_i. For if a_j - a_i = a_m - a_n (with j > i and m > n), then a_j + a_n + a₀ = a_m + a_i + a₀. So either m = j and n = i or m = i and n = j. The latter is not possible since j > i and m > n. So the representation is unique.

Any b_n can be written as b_n - b₀ and hence as a_i - a_j. By the remark above, this representation is unique, so let us write b_n = a_f(n) - a_g(n). Now take m > n > 0. Then b_m - b_n must be a_x - a_y for some x, y. But it is also (a_f(m) - a_g(m)) - (a_f(n) - a_g(n)), so a_f(m) + a_g(n) + a_y = a_f(n) + a_g(m) + a_x. So the f(m), g(n), y is a permutation of f(n), g(m), x. So either f(m) = f(n), g(m) = y, g(n) = x, or g(m) = g(n), f(m) = x, f(n) = y. Hence either f(m) = f(n) and g(m) ≠ g(n), or f(m) ≠ f(n) and g(m) = g(n).

Now suppose for some m > n > 0 we have f(m) = f(n) = c. Then g(m) ≠ g(n). If for some k > 0, f(k) ≠ c, then g(k) = g(m) and g(k) = g(n). Contradiction. So f(k) = c for all k > 0. Hence b_k = a_c - a_g(k). But b_k is a strictly increasing sequence, so a_g(k) is a strictly decreasing sequence. But that means g(k) is a strictly decreasing sequence. That is impossible since there are only finitely many positive integers less than g(1).

Thus we always have f(m) ≠ f(n) for m > n > 0 and hence g(m) = g(n). So b_n = a_f(n) - a_d for some d (*). Hence 0 < f(1) < f(2) < f(3) < ... .

For any m > 0, we have a_m - a₀ = b_u - b_v for some u, v. If v > 0, then we can use (*) to give a_m - a₀ = a_f(u) - a_f(v) with f(u) and f(v) > 0. But that contradicts the uniqueness of the representation a_i - a_j, so we must have v = 0. Hence a_m = b_u. So the set {a₀, a₁, ... } is contained in the set {b₀, b₁, ... }. Also a_m - a₀= a_f(u) - a_d. Hence d = 0. So for any n > 0, (*) gives b_n = a_f(n) and hence the set {b₀, b₁, ... } is contained in the set {a₀, a₁, ... }. So the sets are equal and hence a_k = b_k for all k. 

Problem A7

A polynomial p(x) of degree 2000 with distinct real coefficients satisfies condition n if (1) p(n) = 0 and (2) if q(x) is obtained from p(x) by permuting its coefficients, then either q(n) = 0, or we can obtain a polynomial r(x) by transposing two coefficients of q(x) such that r(n) = 0. Find all integers n for which there is a polynomial satisfying condition n.

 

Solution

Answer: n = 0 and 1.

If p(x) has zero coefficient of x⁰ then it obviously satisfies condition 0. Similarly if p(x) = a₂₀₀₀x²⁰⁰⁰ + ... + a₀ and we put a₀ = a₁ + ... + a₂₀₀₀, then it satisfies condition 1. [In both cases all we need to do to get q(n) = 0 is to get the right coefficient of x⁰.]

It remains to show that if n is not 0 or 1, then p(x) cannot satisfy condition n. We consider first the case |n| > 1. The idea is that we can get too many different values at x = n by permuting the coefficients of p(x) for condition n to hold. Specifically, we claim that we can get at least 2²⁰⁰⁰ different values. Now suppose q(x) = b₂₀₀₀x²⁰⁰⁰ + ... + b₀ is obtained by permuting the coefficients of p(x). Then if we transpose the coefficients b_i and b_j, then we increase the value at x = n by (b_in^j + b_jnⁱ - b_inⁱ - b_jn^j) = d. Now as q(x) ranges over all possibilities and i and j range over all possibilities, d has less than 2001⁴ possible values, because there are 2001 choices for i, 2000 choices for j, then 2001 choices for the coefficient of p(x) which equals b_i and 2000 choices for the coefficient of p(x) which equals b_j. So if q(n) = 0, then r(n) has less than 2001⁴ possible values (where r(x) is obtained from q(x) by transposing two coefficients). But if p(x) satisfies condition n, then r(x) could be any polynomial obtained by permuting the coefficients of p(x). Contradiction, since 2001⁴ < 2²⁰⁰⁰.

Problem C2

A piece is made of 12 unit cubes. It looks like a staircase of 3 steps, each of width 2. Thus the bottom layer is 2 x 3, the second layer is 2 x 2 and the top layer is 1 x 2. For which n can we make an n x n x n cube with such pieces?

 

Solution

Answer: n a multiple of 12.

Obviously a necessary condition is that 12 divides n³ and hence that n is a multiple of 6. Two pieces can be fitted together to form a 2 x 3 x 4 brick. It is easy to use such bricks to form a 12 x 12 x 12 cube and hence an n x n x n cube for n a multiple of 12. So the only case of interest is n = 6 mod 12.

Suppose an n x n x n cube can be made up of the pieces. Label the small cubes with x, y, z coordinates. Color the small cubes with 8 colors according to the parity of the coordinates. Then each small cube in any 2 x 2 x 2 cube will be colored differently, so each cube in the central 2 x 2 x 2 cube of a piece is colored differently. The three small cubes marked x in the diagram below will be colored the same, and similarly the three small cubes behind them. Thus each color appears either one or three times in a piece.

Take one of the colors. Suppose that s pieces have just one cube of that color, and t pieces have three cubes of that color. Then in total there are s + 3t small cubes with the color. But n is even, so the n x n x n cube can be divided into 2 x 2 x 2 cubes and hence there are n³/8 small cubes of each color. There are s + t pieces in total, so n³ = 12(s + t). Hence s + 3t = 12(s + t)/8, so 4s = 12t, and s = 3t. So the total number of pieces is s + t = 4t. Hence the total number of small cubes is 48t = n³. So 16 divides n³ and hence 4 divides n. So we cannot have n = 6 mod 12.

 

Problem C3

n > 3. S = {P₁, ... , P_n} is a set of n points in the plane, no three collinear and no four concyclic. Let a_i be the number of circles through three points of S which have P_i as an interior point. Let m(S) = a₁ + ... + a_n. Show that the points of S are the vertices of a convex polygon iff m(S) = f(n), where f(n) is a value that depends only on n.

 

Solution

Answer: f(n) = 2 n(n-1)(n-2)(n-3)/4!

Consider first the case n = 4. If the convex hull is a triangle, then m(S) = 1. Suppose ABCD is convex. Without loss of generality angle ABD > angle ACD. So B lies inside the circle ACD and C lies outside the circle ABD. Hence A lies outside the circle CBD. Hence D lies inside the circle ABC. So m(S) = 2.

Now consider n > 4 points. Suppose there are c(S) convex subsets of 4 points. Each of those gives 2 circles through 3 points with 1 inside. The other nC4 (binomial n!/( (n-4)! 4!) - c(S) subsets of 4 points give just one such circle. So m(S) = c(S) + nC4. Now put f(n) = 2 (nC4). If m(S) = f(n), the c(S) = nC4, so every subset of 4 points is convex, so S is convex. Conversely, if S is convex, then c(S) = nC4, so m(S) = f(n). 

Problem C4

Find the smallest number of pawns that can be placed on an n x n board such that no row or column contains k adjacent unoccupied squares. Assume that n/2 < k ≤ 2n/3.

 

Solution

Answer: 4(n - k).

Label the squares from 0 to n-1 along each axis. Put pawns on the squares (i, j) with i + j = k-1, 2k-1 or 3k-1. That gives three diagonal lines (or sometimes only two) as shown below (n = 10, k = 6). Note that i, j ≤ n-1 < 2k-1, so i + j < 4k-1, so a pawn goes on every square with i + j + 1 = 0 mod k. It is immediate that no row or column contains k adjacent unoccupied squares. The first diagonal row has k pawns, the second has (2n - 2k) and the third has (2n - 3k). So in total they contain 4(n - k) pawns. We have to show that we cannot do better.

Divide the board into 9 blocks. The corner blocks are (n-k) x (n-k), the center block is (2k-n) x (2k-n) and the others are rectangles, as shown below. Suppose that the middle top block has b rows without pawns. Then there must be at least one pawn in each such row in the block to the left (or the row would have n-k + 2k-n = k adjacent squares without pawns) and another in the block to the right. Similarly, if there are h rows without pawns in the middle bottom block. Similarly, if there are d columns without pawns in the middle left block and f columns without pawns in the middle right block. Note that this may result in double-counting the pawns in the corner blocks.

|  n-k   |  2k-n   |   n-k   |
|        |         |         |   n-k 
|        | --b--   |         |
------------------------------
|        |         |         |
|   d    |         |   f     |  2k-n
|        |         |         |
------------------------------
|        |         |         |
|        |  --h--   |         |   n-k 
|        |         |         |

There are also n-k-b rows with a pawn in the top middle block, and similarly for the other three blocks. So in total, allowing for the possible double counting, there are at least (n-k-b) + (n-k-h) + (n-k-d) + (n-k-f) + (2b + 2h + 2d + 2f)/2 = 4n - 4k pawns.

Problem C5

n rectangles are drawn in the plane. Each rectangle has parallel sides and the sides of distinct rectangles lie on distinct lines. The rectangles divide the plane into a number of regions. For each region R let v(R) be the number of vertices. Take the sum ∑ v(R) over the regions which have one or more vertices of the rectangles in their boundary. Show that this sum is less than 40n.

For example, for the two rectangles illustrated the sum is 28 < 80. Note that the unbounded outer region has 12 vertices, and we do not count the central region because it does not contain any vertices of the two rectangles.

 

Solution

We can classify vertices as convex if the angle inside the region at the vertex is 90^o and concave if it is 270^o. Note that a concave vertex must be a vertex of one of the rectangles. A region has a unique outer boundary and possibly one or more inner boundaries, meaning closed loops which form part of the boundary of the region but whose inside does not form part of the region. For example, the shaded region below has two inner boundaries.

Let a pair (R, P) be a region R and one of its boundaries P. The vertices of the pair are the vertices on P. The number of convex vertices of a pair less the number of concave vertices of the pair is 4 for an outer boundary and -4 for an inner boundary. To see that, lay an arrow along a side of an outer boundary pointing in the anticlockwise direction and move it anticlockwise in a complete circuit of the boundary. It rotates 90^o anticlockwise at a convex vertex and 90^o clockwise at a concave vertex, but it must rotate a total of 360^o anticlockwise in a complete circuit. Similarly for an inner boundary (but the convex and concave vertices are interchanged).

Let N₀ be the number of pairs (R, P) with P an outer boundary which contains at least one of the vertices of the rectangles, and let N₁ be the number of pairs (R, P) with P an inner boundary which contains at least one of the vertices of the rectangles. The rectangles have a total of 4n vertices and each vertex is in at most two outer boundaries. So N₀ <= 8n. On the other hand the unbounded region has an inner boundary which contains at least one of the vertices of the rectangles. So N₁ ≥ 1.

Let B be the set of boundary pairs (R, P) where P contains at least one of the vertices of the rectangles. If b ∈ B, let x_b be the number of convex vertices in P and v_b be the number of concave vertices in P. Then, using the results above, the total number of vertices of regions which have at least one of the rectangles' vertices in their boundaries is ∑_B (x_b + v_b) = ∈_B 2v_b + ∈ (x_b - v_b) = 8n + 4N₀ - 4N₁ ≤ 8n + 4.8n - 4 < 40n.

Problem C6

a and b are positive coprime integers. A subset S of the non-negative integers is called admissible if 0 belongs to S and whenever k belongs to S, so do k + a and k + b. Find f(a, b), the number of admissible sets.

 

Solution

Answer: f(a, b) = ( (a+b)Cb )/(a+b) = (a+b-1)/( a! b! ). p> Every integer k has a unique representation k = ma + nb with m and n integers and 0 ≤ m < b. [That should be reasonably well-known, but a proof is given at the end.] Hence there is a bijection between the integers and the lattice points (m, n) with 0 ≤ m < n. Fill this strip with a standard grid of unit squares and place the number (ma+nb) inside the square with (m, n) as its bottom left vertex. Obviously all the integers above the line n = 0 are non-negative. They must all be included in any admissible set S since 0 ∈ S. All the lattice points below the line ma + nb = 0 are negative, so we are only interested in squares which lie above this line. It runs from (0, 0) to (b, -a). Note that there are no lattice points this segment except for its endpoints, since a and b are relatively prime (if (c, d) was on the segment, then the (negative) slope would be a/b and d/c, which is impossible since a/b is in lowest terms). Thus S is defined by the numbers it contains inside the triangle bounded by m = b, n = 0, ma + nb = 0. The triangle for a = 4, b = 5 is shown below.

However, we do not have complete freedom to include or exclude numbers in the triangle, because if a particular number N is included, then all numbers above and to the right of it must also be included since they are obtained by adding positive multiples of a and/or b. In fact, these are the only numbers in the triangle which must be included if N is included. To prove this we have to show that if we add a to a number on the right hand border of the triangle, then we get a number above the triangle. In other words, we have to show that if ( (b-1)a + nb ) + a = m'a + n'b with 0 ≤ m' < b, then n' ≥ 0. But m'a = ba + nb - n'b = b(a + n - n'), so b must divide m'. Hence m' = 0. But the new number is certainly positive, so n' > 0, as required. Hence the intersection of an admissible set S with the numbers in the triangle is the numbers inside a union of rectangles each with upper right vertex at (b, 0) (the upper right vertex of the triangle). Hence it is all numbers inside the region bounded by the top and right sides of the triangle and a zig-zag line from (0, 0) to (b, -a). This zig-zag line or path has every step downwards or to the right. Also its vertices all lie above the line ma + nb = 0.

Conversely, any such path corresponds to a union of rectangles with upper right vertex at (b, 0) and hence to an admissible set S. So the number of admissible sets is the number of such paths. It is easy to count the paths which only satisfy the first condition (every step downwards or to the right). It is just (a+b)Cb or (a+b)!/( a! b! ). [That should be well-known. But to prove it a path is defined by the order of the unit steps. There are a downward steps and b rightward steps, so the number of paths is the number of ways of picking b objects from a+b. ]

Which of these have all their vertices inside the triangle?

Consider the diagram above. Label the lattice points on the path in sequence P₁, P₂, ... as shown. Now draw a line through each P_i parallel to the line ma + nb = 0. The key point is that all these lines are distinct. For if two points lie on a line then using them to get the slope of the line we have c/d = a/b with c smaller than a contradicting the fact that a/b is in lowest terms. So pick the point P_j with the lowest line (P₇ in the example in the diagram). If we start from (0, 0) but follow the step sequence as if we had started at P_j then we get a path entirely above the line ma + nb = 0. [For clarity, the path is shown starting at P_j in the diagram.]. So, being slightly more formal, suppose the path is (s₁, s₂, ... , s_a+b), where each s_i represents a step downwards or to the right. Then (s₂, s₃, ... , s_a+b, s₁), (s₃, s₄, ... , s_a+b, s₁, s₂) , ... , (s_a+b, s₁, ... , s_a+b-1) are also paths. It is clear from the diagram that the path (s_i+1, s_i+2, ... ) corresponds to the path starting from P_i and that if the line through P_i is a distance d_i above the lowest line through P_j, then the path starting from P_i will dip a maximum distance d_i below the line ma + nb = 0 (when translated to start at (0, 0) ). Since we have shown that all the distances d_i are different, it follows that all the (a+b) cyclically related paths are distinct and that just one of them lies entirely above the line ma + nb = 0.

So the paths divide into ( (a+b)Cb )/(a+b) groups of (a+b) paths with just one path in each group corresponding to an admissible set S. Hence f(a, b) = ( (a+b)Cb )/(a+b) = (a+b-1)/( a! b! ) admissible sets S.

Note

The proof that for relatively prime a, b every integer has a unique representation k = ma + nb with m and n integers and 0 ≤ m < b is as follows.

Let d be the smallest positive integer of the form ma + nb with m and n any integers. We can write a = qd + r with 0 ≤ r < d. But r also has the form ma + nb and it is smaller than d, so it must be 0. Hence d divides a. Similarly, d divides b. But a and b are relatively prime, so d = 1 and ma + nb = 1. So we also have (m + hb)a + (n - ha)b = 1 for any integer h. So by taking a suitable h we can get m+hb into the range 0, 1, ... , b-1. That establishes existence. Suppose k = ma + nb = m'a + n'b with 0 ≤ m, m' < b. Then (m-m')a = (n'-n)b. But a and b are relatively prime, so b must divide m-m'. Since -b < m-m' < b, that implies m = m'. Hence also n = n'.

Problem G1

Two circles C and C' meet at X and Y. Find four points such that if a circle touches C and C' at P and Q and meets the line XY at R and S, then each of the lines PR, PS, QR, QS passes through one of the four points.

 

Solution

Answer: the 4 points are the points of contact of the two common tangents to C and C' (with C and C').

Let PR meet C again at A. Let QR meet C' again at B. We show that AB is tangent to C and C', so that A and B are fixed and independent of the position of the third circle.

Let RU be the tangent at R (as shown). Then ∠QRU = ∠QPR. But RP·RA = RX·RY (PAXY cyclic) = RB.RQ (QBXY cyclic), so RA/RB = RQ/RP and hence RAB and RQP are similar. So ∠QPR = ∠RBA. Hence ∠QRU = ∠RBA and AB is parallel to RX. But it we shrink with center P so that the third circle goes into C, then RU will go into a parallel line through A and hence into AB. But RU is tangent to the third circle, so AB must be tangent to C. Similarly, shrinking about Q, shows that AB is tangent to C'.

A similar argument shows that PS and QS pass through the two points of contact of the other common tangent of C and C'.

Problem G3

ABC is an acute-angled triangle with orthocenter H and circumcenter O. Show that there are points D, E, F on BC, CA, AB respectively such that OD + DH = OE + EH = OF + FH and AD, BE, CF are concurrent.

 

Solution

Extend the altitude AK to meet the circumcircle again at L. Let the line OL meet the circumcircle again at L' and BC at D. We claim that D (and the corresponding points E and E) meet the requirements.

∠BAH = 90^o - B, ∠ABH = 90^o - A, so ∠BHK = (90^o - B) + (90^o - A) = C. But ∠BLK = C (ACLB cyclic). So BHL is isosceles and K is the midpoint of HL. It follows that DH = DL and hence OD + DH = R, the circumradius. Similarly for E and F, so OD + DH = OE + EH = OF + FH.

Now ALA'L' is a rectangle with A'L parallel to BC. Hence D and D' are equally spaced about the midpoint of BC. Similarly for E and E', and F and F'. The lines AD', BE', CF' are concurrent (they pass through O). So by Ceva, (BD')/(D'C) (CE'/E'A) (AF'/F'B) = 1. But BD'/D'C = CD/DB etc, hence (BD/DC) (CE/EA) (AF/FB) = 1, so AD, BE, CF are concurrent by Ceva.

 Problem G4

Show that a convex n-gon can be inscribed in a circle iff there is a pair of real numbers a_i, b_i associated with each vertex P_i such that the distance between each pair of vertices P_iP_j with i < j is a_ib_j - a_jb_i.

 

Solution

Suppose the real numbers exist. By Ptolemy's theorem P₁P₂P₃P₄ is cyclic if (P₁P₃)(P₂P₄) = (P₁P₂)(P₃P₄) + (P₂P₃)(P₁P₄). But rhs = (a₁b₂ - a₂b₁)(a₃b₄ - a₄b₃) + (a₂b₃ - a₃b₂)(a₁b₄ - a₄b₁) = a₁a₃ = a₁a₃b₂b₄ - a₁a₄b₂b₃ - a₂a₃b₁b₄ + a₂a₄b₁b₃ + a₁a₂b₃b₄ - a₂a₄b₁b₃ - a₁a₃b₂b₄ + a₃a₄b₁b₂ = a₁a₂b₃b₄ - a₁a₄b₂b₃ - a₂a₃b₁b₄ + a₃a₄b₁b₂ = lhs. So P₁P₂P₃P₄ is cyclic. Similarly, P₁P₂P₃P_i is cyclic for i = 5, 6, ... , n. So all of P₄, P₅, ... , P_n lie on the circle P₁P₂P₃, so the n-gon is cyclic.

Conversely suppose the n-gon is cyclic. Put a₁ = 0, b₁ = - P₁P₂, a₂ = 1, b₂ = 0, and a_i = P₁P_i/P₁P₂, b_i = P₂P_i for i = 3, 4, ... , n. If 2 < i < j, then P₁P₂P_iP_j is cyclic, so (P₁P_i)(P₂P_j) = (P₁P₂)(P_iP_j) + (P₁P_j)(P₂P_i). Dividing by P₁P₂, we get a_ib_j = P_iP_j + a_jb_i, as required. Also, a₁b₂ - a₂b₁ = 0 + P₁P₂, which is correct. Similarly, a₁b_i - a_ib₁ = 0 + (P₁P_i)/(P₁P₂) x (P₁P₂) = P₁P_i, which is correct. Finally, a₂b_i - a_ib₂ = P₂P_i, which is correct. 

Problem G5

ABC is an acute angled triangle. The tangent at A to the circumcircle meets the tangent at C at the point B'. BB' meets AC at E, and N is the midpoint of BE. Similarly, the tangent at B meets the tangent at C at the point A'. AA' meets BC at D, and M is the midpoint of AD. Show that ∠ABM = ∠BAN. If AB = 1, find BC and AC for the triangles which maximise ∠ABM.

 

Solution

Answer: BC = AC = √2.

We use the triangle ABA' to find x. Let O be the center of the circle and R its radius. Then angle OBA' = 90^o and ∠A'OB = 1/2 ∠BOC = ∠A, so BA' = R tan A. Also ∠AOB = 2∠C, so AB = 2R sin C. ∠A'BA = ∠A, so ∠A'BA = ∠A + ∠B. Hence ∠AA'B = 180^o - ∠A - ∠B - x = ∠C - x. Now from the sine rule, AB/sin AA'B = A'B/sin x. Hence sin(∠C - x) = 2 sin ∠C sin x cot ∠A. So sin ∠C cos x - cos ∠C sin x = 2 sin ∠C sin x cot ∠A. Hence cot x = cot ∠C + 2 cot ∠A.

Applying the sine rule to BMA and BMD gives sin y/sin x = MA/MB = MD/MB = sin MBD/sin MDB = sin(B - y)/sin(B + x), or sin y sin(B + x) = sin x sin(B - y). Expanding and dividing through by sin x sin y sin B gives cot x + cot B = cot y - cot B, or cot y = 2 cot B + cot x = 2 cot A + 2 cot B + cot C. This is symmetric between A and B, so cot ABM = cot BAN. But cot is strictly decreasing over 0^o to 180^o, so ∠ABM = ∠BAN.

We want to maximise ABM or minimise cot ABM and hence minimise 2 cot A + 2 cot B + cot C. But 2 cot A + 2 cot B = 2 sin(A+B)/(sin A sin B) = 4 sin C/(cos(A - B) - cos(A + B) ) = 4 sin C/(cos(A - B) + cos C) ≥ 4 sin C/(1 + cos C) with equality iff A = B. Thus we must take A = B. We then want to minimise 4 sin C/(1 + cos C) + cot C = 4 (2 sin k cos k)/(2 cos²k) + (1 - tan²k)/(tan k + tan k), where k = C/2, and hence to minimise 7/2 tan k + 1/(2 tan k). That is achieved by taking tan k = 1/√7 (eg complete the square), and hence sin C = sin 2k = 2 tan k/(1 + tan²k) = (√7)/4. Since A = B, we have AC = BC and 1 = AB = 2 AC sin k = 2 AC 1/√8. Hence AC = √2. 

Problem G6

ABCD is a convex quadrilateral. The perpendicular bisectors of AB and CD meet at Y. X is a point inside ABCD such that ∠ADX = ∠BCX < 90^o and ∠DAX = ∠CBX < 90^o. Show that ∠AYB = 2 ∠ADX.

 

Solution

Take X' and Y' on the perpendicular bisector of AB so that BX'Y' is similar to BXC (and Y is on the same side of AB as C). Then the triangle BXC can be obtained from BX'Y' by rotating and dilating about B. Hence XX'/BX' = CY'/BY' (obvious, but use similar triangles if you are doubtful). Similarly, AXD is obtained from AX'Y' by rotating and dilating about A. Hence XX'/AX' =Y'D/AY'. But BY' = AY', so CY' = Y'D. Hence Y' = Y. So ∠AYB = 2 ∠AYX = 2 ∠ADX.

Comment

The official solution is appalling. It runs to about 2-3 times the normal length and involves a formidably complicated construction. In general, the official solutions to the shortlist problems are not particularly good, unlike the official solutions to the actual IMO questions. The reason is that the solutions for the IMO questions are updated to reflect good solutions by competitors and others. But the shortlist solution is often no more than the proposer's solution. It is made worse by the fact that the Problem Selection Committee is provided with the proposers' solutions, so often make no independent effort to solve the problems.

Problem G7

Ten gangsters are standing in a field. The distance between each pair of gangsters is different. When the clock strikes, each gangster shoots the nearest gangster dead. What is the largest number of gangsters that can survive?

 

Solution

Answer: 7.

Obviously at least two gangsters die: someone must get shot, but he must shoot someone else. It is easy to arrange for just four to die. Take four roughly in a circle around a fifth. All four shoot the gangster in the center, and he shoots one of those in the circle. So two out of the five die. Arrange the other five similarly, some distance away. However, with a little care, we can reduce that to three gangsters dying, by arranging that the two central gangsters both shoot the same gangster. Consider the situation below. The lh circle is slightly smaller than the rh circle. The angles 142, 243, 7 10 8, 9 10 8 are slightly greater than 60^o. The distance 56 is the same as the radius of the larger circle. Thus 1, 2, 3 and 5 shoot 4; 4, 6 and 10 shoot 5; 7, 8 and 9 shoot 10. So 4, 5, 10 die and the others survive.

So we have to show that we cannot have just two gangsters die. It is surprisingly difficult.

We cannot have six gangsters all shooting the same person. For suppose A, B, C, D, E, F all shoot O. Suppose ∠AOB ≤ 60^o. Since OA and OB are assumed to be unequal, angles OAB and OBA are unequal. Hence at least one of them > 60^o. Suppose it is ∠OAB. Then ∠OAB > ∠AOB, then OB > BA, so B should shoot A not O. Contradiction. Similarly, if ∠OBA > 60^o. So ∠OAB > 60^o. Similarly, each of the other angles BOC, COD, DOE, EOF, FOA must be > 60^o. But the sum of the six angles is 360^o. Contradiction. So at most 5 gangsters can shoot the same person.

So assume that it is possible to arrange 10 gangsters so that only two die. Let A and B be the two closest gangsters. Then they must shoot each other. So we have to show that every other gangster shoots A or B. Since at most 5 gangsters can shoot the same person, 4 of the others must shoot A and 4 must shoot B. Using the result in the previous paragraph if C is the next gangster anticlockwise from B who shoots A and C' the next gangster clockwise then, the ∠CAC' < 180^o. Take the line through B parallel to AC (the dotted line in the diagram below). If D and D' are the two gangsters either side of A in the group who shoot B, then ∠DBD' < 180^o, so either D or D' lies in the strip between the two parallel lines. Hence we may take ∠CAB + ∠ABD < 180^o (for if it is not, then ∠C'AB + ∠ABD' < 180^o and we just relabel).

D is closer to B than A (by assumption), so it lies on the same side of the perpendicular bisector of AB as B. Similarly, C lies on the same side as A. So the quadrilateral ABDC has its vertices in that order (with no sides intersecting except at vertices). Now CA < CD (since C shoots A not D). So ∠CDA < ∠CAD. Hence ∠CDA < 90^o. BA is the shortest side of ABD, so ∠ADB < 90^o. Hence ∠CDB < 180^o. Similarly, ∠ACD < 180^o. So ABDC is convex. Label the angles a, b, c, d as shown below.

We have ∠HAB = b + ∠ACB < 2b (since AB > AC). Similarly ∠GBA = a + ∠ADB < 2a. So 2a + 2b > ∠HAB + ∠GBA > 180^o. Similarly, ∠ECD = d + ∠CAD > 2d (since CD > CA) and ∠FDC = c + ∠DBC > 2c, so 2c + 2d < ∠ECD + ∠FDC < 180^o. Hence c + d < a + b. Contradiction, since they are obviously equal. 

Problem N1

Find all positive integers n > 1 such that if a and b are relatively prime then a = b mod n iff ab = 1 mod n.

 

Solution

Answer: 2, 3, 4, 6, 8, 12, 24.

Since a = b mod n, the condition is equivalent to a² = 1 mod n for all a relatively prime to n. Suppose n = ∏ p^e(p), then we claim that a² = 1 mod n for all a relatively prime to n iff a² = 1 mod p^e(p) mod p^e(p) for each prime factor p of n (and a relatively prime to p). The if part is obvious: if a is relatively prime to n, then it is relatively prime to each p^e(p), so a² = 1 mod p^e(p), so a² = 1 mod n. To prove the only if part, suppose a is relatively prime to p. Let r, s, ... be the primes dividing n which do not divide a. Then a + p^e(p)(rs...) is relatively prime to n. So (a + p^e(p)(rs...) )² = 1 mod n. So it must also be 1 mod p^e(p). But (a + p^e(p)(rs...) )² = a² mod p^e(p), so a² = 1 mod p^e(p) as required.

It is easy to check that a² = 1 mod 8 for any odd integer a. Hence also a² = 1 mod 2 and mod 4 for any odd integer a. But 3² = 9, which is not 1 mod 2^k for k > 3. Similarly, it is easy to check that 1² = 2² = 1 mod 3, but 2² = 4, which is not 1 mod 3^k for k > 1. Finally 2² = 4, which is not 1 mod p^k for p > 3. So n cannot be divisible by any primes except 2 and 3, and it is not divisible by 16 or 9. On the other hand, if n = 2^h3^k with h = 0, 1, 2 or 3 and k = 0 or 1, then we have established that a² = 1 mod 2^h for any a relatively prime to 2, and a² = 1 mod 3^k for any a relatively prime to k, so that a² = 1 mod n for any a relatively prime to n.

 

Problem N2

Find all positive integers n such that the number of positive divisors of n is (4n)^1/3.

 

Solution

Answer: 2, 128, 2000.

Let e(p) be the exponent of p in the prime factorisation of n (so n = 2^e(2)3^e(3)5^e(5) ... ). Since 4n is a cube, we must have e(2) = 1 mod 3 and e(p) = 0 mod 3 for odd p. Let d(n) be the number of positive divisors of n. Then d(n) = (1 + e(2) )(1 + e(3) )(1 + e(5) ) ... . Now 1 + e(2) = 2 mod 3 and 1 + e(p) = 1 mod 3 for p > 2, so d(n) is not a multiple of 3. But 4n = d(n)³, so n is not a multiple of 3, so e(3) = 0.

Put e(2) = 3k + 1, and e(p) = 3 f(p) for odd primes p. Then d(n) = (4n)^1/3 gives (3k + 2) ∏_p>3 (1 + 3 f(p) ) = 2^k+1 ∏_p>3 p^f(p). So (3k + 2)/2^k+1 = ∏_p>3 p^f(p)/(1 + 3 f(p) ) (*).

Now for p ≥ 5, we have p^f(p) ≥ (1 + 4)^f(p) ≥ 1 + 4 f(p) > 1 + 3 f(p), unless f(p) = 0. So the rhs of (*) is > 1 if any odd prime > 5 divides n and = 1 if not. But 2^k+1 > 2 + 3k for k > 2 (eg a trivial induction). So the lhs of (*) is < 1 for k > 2. So we must have k = 0, 1 or 2.

If k = 0 or 2, then 2^k+1 = 2 + 3k, so the rhs of (*) is 1, so n has no prime factors except 2. That gives the solutions n = 2, 128. If k = 1, then (3k + 2)/2^k+1 = 5/4. Now if p >= 7, then p^h ≥ (1 + 6)^h ≥ 1 + 6h. So if n has a prime factor greater than 5, then the rhs of (*) is at least (1 + 6h)/(1 + 3h) with h ≥ 1, and hence at least 3/2 ( h ≥ 1 implies 3/2h > 1/2 implies 1 + 6h > 3/2 (1 + 3h) ). So n cannot have a prime factor greater than 5. Suppose f(5) = h. Then (*) gives 5/4 = 5^h/(1 + 3h), which implies h = 1 (5^h/(1 + 3h) is a strictly increasing function of h, so h = 1 is the only solution). Thus we get n = 2⁴5³ = 2000.

Problem N4

Find all positive integers a, m, n such that a^m + 1 divides (a + 1)ⁿ.

 

Solution

Answer: (a, m, n) = (1, m, n), (a, 1, n) or (2, 3, k) where k > 1.

It is obvious that (1, m, n) and (a, 1, n) are solutions, so assume a > 1 and m > 1. We show first that m must be odd.

Suppose there is an odd prime p dividing a^m + 1. Then p must also divide (a + 1)ⁿ and hence (a + 1). So a = -1 mod p, so a^m + 1 = (-1)^m + 1 mod p. Hence m is odd. If there is no such prime p, then a^m + 1 = 2^k for some k. But a and m are assumed to be at least 2, so a^m + 1 must be at least 5 and hence k ≥ 3. So a^m = -1 mod 4. But squares can only be 0 or 1 mod 4, so a^m cannot be a square, so m must be odd.

Suppose p divides m. Then (since m is odd) a^p + 1 divides a^m + 1 and hence (a + 1)ⁿ. But p is odd, so a + 1 divides a^p + 1 and (a^p + 1)/(a + 1) = a^p-1 - a^p-2 + a^p-3 - ... - p + 1 divides (a + 1)^n-1. Put f(x) = x^p-1 - x^p-2 + ... - x + 1. Then f(-1) = p, so f(x) - p = (x + 1) g(x) for some polynomial g(x). Putting x = a, we get f(a) = (a + 1) g(a) + p. If a prime q divides f(a), then since f(a) divides (a + 1)^n-1, q must divide (a + 1). Hence q divides p, so q = p. So f(a) = p^k for some k ≥ 1. Since f(a) divides (a + 1)^n-1, p must divide a + 1.

We show next that k = 1, so f(a) = p. If p² divides (a + 1), then f(a) = (a + 1) g(a) + p implies that p² does not divide f(a). If p² does not divide (a + 1), then (a + 1) = ph (with h not divisible by p). So f(a) = (a^p + 1)/(a + 1) = ( (1 + ph - 1)^p)/ph = ( 1 - 1 + p²h + terms divisible by p³)/ph = p mod p², so again p² does not divide f(a). So in any case f(a) = p.

Now (a² - a) ≥ 2, (a⁴ - a³) ≥ 8 and obviously (a^2r - a^2r-1) ≥ 2 for r ≥ 2. So f(a) ≥ 11 > 5 for p = 5, and hence by a trivial induction f(a) > p for p > 5. So the only possibility is p = 3. Then we have a² - a + 1 = 3 and hence a = 2.

So far we have established that a = 2 and that m is a power of 3. But (2⁹ + 1) = 513, which is not a power of 3 and so cannot divide (2 + 1)ⁿ. But (2²⁷ + 1), (2⁸¹ + 1), ... are all divisible by (2⁹ + 1) and hence are also not powers of 3. So m must be 3. Finally, we require that (a^m + 1) = 9 divides (2 + 1)ⁿ, so n ≥ 2.

 

Problem N5

Show that for infinitely many positive integers n, we can find a triangle with integral sides whose semiperimeter divided by its inradius is n.

 

Solution

Let the sides be a, b, c the semiperimeter s = (a + b + c)/2, the inradius r, and the area A. We have A = sr, A² = s(s - a)(s - b)(s - c) (Heron's formula) and s = nr (given). So nA = nsr = s². So s⁴ = n²s(s - a)(s - b)(s - c). Hence (2s)³ = n²(2s - 2a)(2s - 2b)(2s - 2c). Putting x = -a + b + c, y = a - b + c, z = a + b - c, this becomes (x + y + z)³ = n²xyz (*).

Conversely, if we can find positive integers x, y, z satisfying (*), then 2x, 2y, 2z also satisfy (*) so we may assume x, y, z are even. Then we can find a, b, c such that x = -a + b + c etc by taking c = (x+y)/2, b = (x+z)/2, a = (y+z)/2. So s⁴ = n²A² and hence s² = nA = nsr. Hence s = nr. Thus it is sufficient to show that we can find a positive integer solution (in x, y, z) to (*) for infinitely many n.

We look for solutions with z = k(x + y), n = 3(k + 1). We require (x + y)³(k + 1)³ = 9(k + 1)²xyk(x + y), or (x + y)²(k + 1) = 9kxy. Put w = x/y. Then (1 + w)²(k + 1) = 9kw or w²(k + 1) - (7k - 2)w + (k + 1) = 0. We require w to be rational, so it is sufficient if (7k - 2)² - 4(k + 1)² = 9k(5k - 4) is a square. So it is sufficient if k = u² and 5u² - 4 = v².

This equation has infinitely many solutions, for (u, v) = (1, 1) is a solution and if (u, v) is a solution, then u' = (3u + v)/2, v' = (5u + 3v)/2 is also a solution. To establish this we show that (1) 5u'² - 4 = v'², (2) u > u' and v > v', (3) u' and v' are both integers. For (1), we have 5(3u + v)² - (5u + 3v)² = 45u² + 30uv + 5v² - 25u² - 30uv - 9v² = 20u² - 4v² = 4(5u² - v²) = 16, as required. For (2), we note that u' and v' are certainly positive, so u' > 3u/2 > u, and v' > 3v/2 > v. For (3) we claim that u and v are integral and have the same parity. Hence 3u + v and 5u + 3v are both even and so u' and v' are integral. Also u' + v' = (8u + 4v)/2 = 4u + 2v, which is even, so u' and v' have the same parity.

Thus we can find an infinite sequence of integral pairs (u, v) with u and v strictly increasing. That gives an infinite strictly increasing sequence of values of k which yield rational w. Then if w = r/s, we may take x = r, y = s, z = k(x + y) as a solution for n = 3(k + 1). So we get solutions for infinitely many n.

For example, the second member of the sequence (u, v) is (2, 4). That gives k = 4, and w satisfies 5w² - 26w + 5 = 0, so w = (26 ± 24)/10 = 5 or 1/5. So n = 15 and we may take x = 1, y = 5, z = 24. Then (x + y + z)³ = 30³, and n²xyz = 15²5.3.8 = 30³. So x = 2, y = 10, z = 48 is also a solution. So a = 29, b = 25, c = 6. Hence s = 30. So A² = s(s - a)(s - b)(s - c) = 30.1.5.24 = 60². So r = A/s = 2 and s = nr, as required.

Problem N6

Show that all but finitely many positive integers can be represented as a sum of distinct squares.

 

Solution

The key idea is to write 29 = 2² + 5², 2.29 = 3² + 7². Now given any positive integer n, write n in binary, so n is a sum of distinct powers of 2. Let r be the sum of the odd powers of 2, and s the sum of the even powers of 2. So n = r + s, and we have r = (2^a + 2^b + ... ), where 1 ≤ a < b < ... . Similarly, s = (2ⁱ + 2^j + ... ), where 0 ≤ i < j < ... .

Now 4.29 r = (3² + 7²) x 2r = 3²( a sum of distinct even powers of 2, all ≥ 4) + 7²( a sum of distinct even powers of 2, all >= 4). Similarly, 4.29 s = (2² + 5²) x 4s = 2²( a sum of distinct even powers of 2, all >= 4) + 5²( a sum of distinct even powers of 2, all ≥ 4). Thus 4.29 n = a sum of distinct even squares. For example, if n = 79, we have n = 1 + 2 + 4 + 8 + 64 = (1 + 4 + 64) + (2 + 8), so 4.49 n = (2² + 5²)(4 + 16 + 256) + (3² + 7²)(4 + 16) = 4² + 8² + 32² + 10² + 20² + 80² + 6² + 12² + 14² + 28².

We can write any integer n as 116q + r with 0 ≤ r < 116. Now r = 1² + (58 + 1)² + (58.2 + 1)² + (58.3 + 1)² + ... + (58(r-1) + 1)² mod 116 (because (58k + 1)² = 1 + 116k + 58²k² = 1 mod 116 and there are r squares in the sum). So provided n > K = 1² + (58.1 + 1)² + ... + (58.114 + 1)², we can write n = 1² + (58.1 + 1)² + ... + (58(r-1) + 1)² + 116k for some non-negative k. Now we are home, because the squares are all odd and distinct, whereas 116k can be written as a sum of distinct even squares.

Note that several small integers cannot be written as a sum of distinct squares. For example, 2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31.

Read more »

Posted in: IMO shortlist