Duˇ san Djuki? c Vladimir Jankovi? c Ivan Mati? c Nikola Petrovi? c
IMO Shortlist 2005
From the book ”The IMO Compendium”
c 2006 Springer Science+Busi
ness Media, Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, Inc. 233, Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholary analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar items, even if they are not identi?ed as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.
1.1 The Forty-Sixth IMO M? erida, Mexico, July 8–19, 2005
1.1.1 Contest Problems First Day (July 13) 1. Six points are chosen on the sides of an equilateral triangle ABC : A1 , A2 on BC ; B1 , B2 on CA; C1 , C2 on AB . These points are vertices of a convex hexagon A1 A2 B1 B2 C1 C2 with equal side lengths. Prove that the lines A1 B2 , B1 C2 and C1 A2 are concurrent. 2. Let a1 , a2 , . . . be a sequence of integers with in?nitely many positive terms and in?nitely many negative terms. Suppose that for each positive integer n, the numbers a1 , a2 , . . . , an leave n di?erent remainders on division by n. Prove that each integer occurs exactly once in the sequence. 3. Let x, y and z be positive real numbers such that xyz ≥ 1. Prove that y5 ? y2 z5 ? z2 x5 ? x2 + + ≥ 0. x5 + y 2 + z 2 y 5 + z 2 + x2 z 5 + x2 + y 2 Second Day (July 14) 4. Consider the sequence a1 , a2 , . . . de?ned by an = 2 n + 3 n + 6 n ? 1 (n = 1, 2, . . . ).
Determine all positive integers that are relatively prime to every term of the sequence. 5. Let ABCD be a given convex quadrilateral with sides BC and AD equal in length and not parallel. Let E and F be interior points of the sides
BC and AD respectively such that BE = DF . The lines AC and BD meet at P , the lines BD and EF meet at Q, the lines EF and AC meet at R. Consider all the triangles P QR as E and F vary. Show that the circumcircles of these triangles have a common point other than P . 6. In a mathematical competition 6 problems were posed to the contestants. Each pair of problems was solved by more than 2/5 of the contestants. Nobody solved all 6 problems. Show that there were at least 2 contestants who each solved exactly 5 problems. 1.1.2 Shortlisted Problems 1. A1 (ROM) Find all monic polynomials p(x) with integer coe?cients of degree two for which there exists a polynomial q (x) with integer coe?cients such that p(x)q (x) is a polynomial having all coe?cients ±1. 2. A2 (BUL) Let R+ denote the set of positive real numbers. Determine all functions f : R+ → R+ such that f (x)f (y ) = 2f (x + yf (x)) for all positive real numbers x and y . 3. A3 (CZE) Four real numbers p, q, r, s satisfy p+q+r+s=9 and p2 + q 2 + r2 + s2 = 21.
Prove that ab ? cd ≥ 2 holds for some permutation (a, b, c, d) of (p, q, r, s). 4. A4 (IND) Find all functions f : R → R satisfying the equation f (x + y ) + f (x)f (y ) = f (xy ) + 2xy + 1 for all real x and y . 5. A5 (KOR)IMO3 Let x, y and z be positive real numbers such that xyz ≥ 1. Prove that x5 ? x2 y5 ? y2 z5 ? z2 + + ≥ 0. x5 + y 2 + z 2 y 5 + z 2 + x2 z 5 + x2 + y 2 6. C1 (AUS) A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are o?.
1.1 Copyright c : The Authors and Springer
7. C2 (IRN) Let k be a ?xed positive integer. A company has a special method to sell sombreros. Each customer can convince two persons to buy a sombrero after he/she buys one; convincing someone already convinced does not count. Each of these new customers can convince two others and so on. If each one of the two customers convinced by someone makes at least k persons buy sombreros (directly or indirectly), then that someone wins a free instructional video. Prove that if n persons bought sombreros, then at most n/(k + 2) of them got videos. 8. C3 (IRN) In an m × n rectangular board of mn unit squares, adjacent squares are ones with a common edge, and a path is a sequence of squares in which any two consecutive squares are adjacent. Each square of the board can be colored black or white. Let N denote the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge, and let M denote the number of colorings in which there exist at least two non-intersecting black paths from the left edge to the right edge. Prove that N 2 ≥ 2mn M . 9. C4 (COL) Let n ≥ 3 be a given positive integer. We wish to label each side and each diagonal of a regular n-gon P1 . . . Pn with a positive integer less than or equal to r so that: (i) every integer between 1 and r occurs as a label; (ii) in each triangle Pi Pj Pk two of the labels are equal and greater than the third. Given these conditions: (a) Determine the largest positive integer r for which this can be done. (b) For that value of r, how many such labellings are there? 10. C5 (SMN) There are n markers, each with one side white and the other side black, aligned in a row so that their white sides are up. In each step, if possible, we choose a marker with the white side up (but not one of outermost markers), remove it and reverse the closest marker to the left and the closest marker to the right of it. Prove that one can achieve the state with only two markers remaining if and only if n ? 1 is not divisible by 3. 11. C6 (ROM)IMO6 In a mathematical competition 6 problems were posed to the contestants. Each pair of problems was solved by more than 2/5 of the contestants. Nobody solved all 6 problems. Show that there were at least 2 contestants who each solved exactly 5 problems. 12. C7 (USA) Let n ≥ 1 be a given integer, and let a1 , . . . , an be a sequence of integers such that n divides the sum a1 + · · · + an . Show that there exist permutations σ and τ of 1, 2, . . . , n such that σ (i) + τ (i) ≡ ai (mod n) for all i = 1, . . . , n. 13. C8 (BUL) Let M be a convex n-gon, n ≥ 4. Some n ? 3 of its diagonals are colored green and some other n ? 3 diagonals are colored red, so that
no two diagonals of the same color meet inside M . Find the maximum possible number of intersection points of green and red diagonals inside M. 14. G1 (GRE) In a triangle ABC satisfying AB + BC = 3AC the incircle has center I and touches the sides AB and BC at D and E , respectively. Let K and L be the symmetric points of D and E with respect to I . Prove that the quadrilateral ACKL is cyclic. 15. G2 (ROM)IMO1 Six points are chosen on the sides of an equilateral triangle ABC : A1 , A2 on BC ; B1 , B2 on CA; C1 , C2 on AB . These points are vertices of a convex hexagon A1 A2 B1 B2 C1 C2 with equal side lengths. Prove that the lines A1 B2 , B1 C2 and C1 A2 are concurrent. 16. G3 (UKR) Let ABCD be a parallelogram. A variable line l passing through the point A intersects the rays BC and DC at points X and Y , respectively. Let K and L be the centers of the excircles of triangles ABX and ADY , touching the sides BX and DY , respectively. Prove that the size of angle KCL does not depend on the choice of the line l. 17. G4 (POL)IMO5 Let ABCD be a given convex quadrilateral with sides BC and AD equal in length and not parallel. Let E and F be interior points of the sides BC and AD respectively such that BE = DF . The lines AC and BD meet at P , the lines BD and EF meet at Q, the lines EF and AC meet at R. Consider all the triangles P QR as E and F vary. Show that the circumcircles of these triangles have a common point other than P . 18. G5 (ROM) Let ABC be an acute-angled triangle with AB = AC , let H be its orthocenter and M the midpoint of BC . Points D on AB and E on AC are such that AE = AD and D, H, E are collinear. Prove that HM is orthogonal to the common chord of the circumcircles of triangles ABC and ADE . 19. G6 (RUS) The median AM of a triangle ABC intersects its incircle ω at K and L. The lines through K and L parallel to BC intersect ω again at X and Y . The lines AX and AY intersect BC at P and Q. Prove that BP = CQ. 20. G7 (KOR) In an acute triangle ABC , let D, E , F , P , Q, R be the feet of perpendiculars from A, B , C , A, B , C to BC , CA, AB , EF , F D, DE , respectively. Prove that p(ABC )p(P QR) ≥ p(DEF )2 , where p(T ) denotes the perimeter of triangle T . 21. N1 (POL)IMO4 Consider the sequence a1 , a2 , . . . de?ned by an = 2 n + 3 n + 6 n ? 1 (n = 1, 2, . . . ).
Determine all positive integers that are relatively prime to every term of the sequence.
1.1 Copyright c : The Authors and Springer
22. N2 (NET)IMO2 Let a1 , a2 , . . . be a sequence of integers with in?nitely many positive terms and in?nitely many negative terms. Suppose that for each positive integer n, the numbers a1 , a2 , . . . , an leave n di?erent remainders on division by n. Prove that each integer occurs exactly once in the sequence. 23. N3 (MON) Let a, b, c, d, e and f be positive integers. Suppose that the sum S = a + b + c + d + e + f divides both abc + def and ab + bc + ca ? de ? ef ? f d. Prove that S is composite. 24. N4 (COL) Find all positive integers n > 1 for which there exists a unique integer a with 0 < a ≤ n! such that an + 1 is divisible by n!. 25. N5 (NET) Denote by d(n) the number of divisors of the positive integer n. A positive integer n is called highly divisible if d(n) > d(m) for all positive integers m < n. Two highly divisible integers m and n with m < n are called consecutive if there exists no highly divisible integer s satisfying m < s < n. (a) Show that there are only ?nitely many pairs of consecutive highly divisible integers of the form (a, b) with a|b. (b) Show that for every prime number p there exist in?nitely many positive highly divisible integers r such that pr is also highly divisible. 26. N6 (IRN) Let a and b be positive integers such that an + n divides bn + n for every positive integer n. Show that a = b. 27. N7 (RUS) Let P (x) = an xn + an?1 xn?1 + · · · + a0 , where a0 , . . . , an are integers, an > 0, n ≥ 2. Prove that there exists a positive integer m such that P (m!) is a composite number.
2.1 Solutions to the Shortlisted Problems of IMO 2005
1. Clearly, p(x) has to be of the form p(x) = x2 + ax ± 1 where a is an integer. For a = ±1 and a = 0 polynomial p has the required property: it su?ces to take q = 1 and q = x + 1, respectively. Suppose now that |a| ≥ 2. Then p(x) has two real roots, say x1 , x2 , which are also roots of p(x)q (x) = xn + an?1 xn?1 + · · · + a0 , ai = ±1. Thus 1= a0 1 1 1 an?1 + ··· + n ≤ < + ··· + n xi xi |xi | |xi | |xi | ? 1
which implies |x1 |, |x2 | < 2. This immediately rules out the case |a| ≥ 3 and the polynomials p(x) = x2 ± 2x ? 1. The remaining two polynomials x2 ± 2x + 1 satisfy the condition for q (x) = x ? 1. Summing all, the polynomials p(x) with the desired property are x2 ± x ± 1, x2 ± 1 and x2 ± 2x + 1. 2. Given y > 0, consider the function ?(x) = x + yf (x), x > 0. This function is injective: indeed, if ?(x1 ) = ?(x2 ) then f (x1 )f (y ) = f (?(x1 )) = f (?(x2 )) = f (x2 )f (y ), so f (x1 ) = f (x2 ), so x1 = x2 by the de?nition of ?. Now if x1 > x2 and f (x1 ) < f (x2 ), we have ?(x1 ) = ?(x2 ) for 1 ?x 2 > 0, which is impossible; hence f is non-decreasing. The y = f (xx 2 )?f (x 1 ) functional equation now yields f (x)f (y ) = 2f (x + yf (x)) ≥ 2f (x) and consequently f (y ) ≥ 2 for y > 0. Therefore f (x + yf (x)) = f (xy ) = f (y + xf (y )) ≥ f (2x) holds for arbitrarily small y > 0, implying that f is constant on the interval (x, 2x] for each x > 0. But then f is constant on the union of all intervals (x, 2x] over all x > 0, that is, on all of R+ . Now the functional equation gives us f (x) = 2 for all x, which is clearly a solution. Second Solution. In the same way as above we prove that f is nondecreasing, hence it