IMO 2004 SL N7

Let p be an odd prime and n a positive integer. In the

imoshortlistmathematicsolympiadnumber theory

IMO 2004 SL N7

Origin: BUL | Category: Number Theory

Problem

Let p be an odd prime and n a positive integer. In the coordinate plane, eight distinct points with integer coordinates lie on a circle with diameter of length pn. Prove that there exists a triangle with vertices at three of the given points such that the squares of its side lengths are integers divisible by pn+1.

Solution

We shall denote by k the given circle with diameter pn. Let A, B be lattice points (i.e., points with integer coordinates). We shall denote by µ(AB) the exponent of the highest power of p that divides the integer AB2. We observe that if S is the area of a triangle ABC where A, B, C are lattice points, then 2S is an integer. According to Heron’s formula and the formula for the circumradius, a triangle ABC whose circumcenter has diameter pn satisfies 2AB2BC2 + 2BC2CA2 + 2CA2AB2 −AB4 −BC4 −CA4 = 16S2 (1) and AB2 \cdot BC2 \cdot CA2 = (2S)2p2n. (2) Lemma 1. Let A, B, and C be lattice points on k. If none of AB2, BC2, CA2 is divisible by pn+1, then µ(AB), µ(BC), µ(CA) are 0, n, n in some order. Proof. Let k = min{µ(AB), µ(BC), µ(CA)}. By (1), (2S)2 is divisible by p2k. Together with (2), this gives us µ(AB) + µ(BC) + µ(CA) = 2k + 2n. On the other hand, if none of AB2, BC2, CA2 is divisible by pn+1, then µ(AB) + µ(BC) + µ(CA) \leqk + 2n. Therefore k = 0 and the remaining two of µ(AB), µ(BC), µ(CA) are equal to n. Lemma 2. Among every four lattice points on k, there exist two, say M, N, such that µ(MN) \geqn + 1. Proof. Assume that this doesn’t hold for some points A, B, C, D on k. By Lemma 1, µ for some of the segments AB, AC, . . . , CD is 0, say µ(AC) = 0. It easily follows by Lemma 1 that then µ(BD) = 0 and µ(AB) = µ(BC) = µ(CD) = µ(DA) = n. Let a, b, c, d, e, f \inN be

such that AB2 = pna, BC2 = pnb, CD2 = pnc, DA2 = pnd, AC2 = e, BD2 = f. By Ptolemy’s theorem we have \sqrtef = pn \sqrtac + \sqrt bd

. Taking squares, we get that ef p2n = \sqrtac + \sqrt bd = ac + bd + 2 \sqrt abcd is rational and hence an integer. It follows that ef is divisible by p2n, a contradiction. Now we consider eight lattice points A1, A2, . . . , A8 on k. We color each segment AiAj red if µ(AiAj) > n and black otherwise, and thus obtain a graph G. The degree of a point X will be the number of red segments with an endpoint in X. We distinguish three cases: (i) There is a point, say A8, whose degree is at most 1. We may suppose w.l.o.g. that A8A7 is red and A8A1, . . . , A8A6 black. By a well-known fact, the segments joining vertices A1, A2, . . . , A6 determine either a red triangle, in which case there is nothing to prove, or a black triangle, say A1A2A3. But in the latter case the four points A1, A2, A3, A8 do not determine any red segment, a contradiction to Lemma 2. (ii) All points have degree 2. Then the set of red segments partitions into cycles. If one of these cycles has length 3, then the proof is complete. If all the cycles have length at least 4, then we have two possibilities: two 4-cycles, say A1A2A3A4 and A5A6A7A8, or one 8-cycle, A1A2 . . . A8. In both cases, the four points A1, A3, A5, A7 do not determine any red segment, a contradiction. (iii) There is a point of degree at least 3, say A1. Suppose that A1A2, A1A3, and A1A4 are red. We claim that A2, A3, A4 determine at least one red segment, which will complete the solution. If not, by Lemma 1, µ(A2A3), µ(A3A4), µ(A4A2) are n, n, 0 in some order. Assuming w.l.o.g. that µ(A2A3) = 0, denote by S the area of triangle A1A2A3. Now by formula (1), 2S is not divisible by p. On the other hand, since µ(A1A2) \geqn + 1 and µ(A1A3) \geqn + 1, it follows from (2) that 2S is divisible by p, a contradiction.

A Notation and Abbreviations A.1 Notation We assume familiarity with standard elementary notation of set theory, alge- bra, logic, geometry (including vectors), analysis, number theory (including divisibility and congruences), and combinatorics. We use this notation liber- ally. We assume familiarity with the basic elements of the game of chess (the move- ment of pieces and the coloring of the board). The following is notation that deserves additional clarification. ◦B(A, B, C), A −B −C: indicates the relation of betweenness, i.e., that B is between A and C (this automatically means that A, B, C are different collinear points). ◦A = l1 \capl2: indicates that A is the intersection point of the lines l1 and l2. ◦AB: line through A and B, segment AB, length of segment AB (depending on context). ◦[AB: ray starting in A and containing B. ◦(AB: ray starting in A and containing B, but without the point A. ◦(AB): open interval AB, set of points between A and B. ◦[AB]: closed interval AB, segment AB, (AB) \cup{A, B}. ◦(AB]: semiopen interval AB, closed at B and open at A, (AB) \cup{B}. The same bracket notation is applied to real numbers, e.g., [a, b) = {x | a \leqx < b}. ◦ABC: plane determined by points A, B, C, triangle ABC (\triangleABC) (de- pending on context). ◦[AB, C: half-plane consisting of line AB and all points in the plane on the same side of AB as C.

A Notation and Abbreviations ◦(AB, C: [AB, C without the line AB. ◦⟨−\toa , −\tob ⟩, −\toa \cdot −\tob : scalar product of −\toa and −\tob . ◦a, b, c, \alpha, \beta, \gamma: the respective sides and angles of triangle ABC (unless oth- erwise indicated). ◦k(O, r): circle k with center O and radius r. ◦d(A, p): distance from point A to line p. ◦SA1A2...An: area of n-gon A1A2 . . . An (special case for n = 3, SABC: area of \triangleABC). ◦N, Z, Q, R, C: the sets of natural, integer, rational, real, complex numbers (respectively). ◦Zn: the ring of residues modulo n, n \inN. ◦Zp: the field of residues modulo p, p being prime. ◦Z[x], R[x]: the rings of polynomials in x with integer and real coefficients respectively. ◦R∗: the set of nonzero elements of a ring R. ◦R[\alpha], R(\alpha), where \alpha is a root of a quadratic polynomial in R[x]: {a + b\alpha | a, b \inR}. ◦X0: X \cup{0} for X such that 0 /\inX. ◦X+, X−, aX + b, aX + bY : {x | x \inX, x > 0}, {x | x \inX, x < 0}, {ax + b | x \inX}, {ax + by | x \inX, y \inY } (respectively) for X, Y \subseteqR, a, b \inR. ◦[x], \lfloorx\rfloor: the greatest integer smaller than or equal to x. ◦\lceilx\rceil: the smallest integer greater than or equal to x. The following is notation simultaneously used in different concepts (depending on context). ◦|AB|, |x|, |S|: the distance between two points AB, the absolute value of the number x, the number of elements of the set S (respectively). ◦(x, y), (m, n), (a, b): (ordered) pair x and y, the greatest common divisor of integers m and n, the open interval between real numbers a and b (respectively). A.2 Abbreviations We tried to avoid using nonstandard notations and abbreviations as much as possible. However, one nonstandard abbreviation stood out as particularly convenient:

A.2 Abbreviations ◦w.l.o.g.: without loss of generality. Other abbreviations include: ◦RHS: right-hand side (of a given equation). ◦LHS: left-hand side (of a given equation). ◦QM, AM, GM, HM: the quadratic mean, the arithmetic mean, the geo- metric mean, the harmonic mean (respectively). ◦gcd, lcm: greatest common divisor, least common multiple (respectively). ◦i.e.: in other words. ◦e.g.: for example.

B Codes of the Countries of Origin ARG Argentina ARM Armenia AUS Australia AUT Austria BEL Belgium BLR Belarus BRA Brazil BUL Bulgaria CAN Canada CHN China COL Colombia CUB Cuba CYP Cyprus CZE Czech Republic CZS Czechoslovakia EST Estonia FIN Finland FRA France FRG Germany, FR GBR United Kingdom GDR Germany, DR GEO Georgia GER Germany GRE Greece HKG Hong Kong HUN Hungary ICE Iceland INA Indonesia IND India IRE Ireland IRN Iran ISR Israel ITA Italy JAP Japan KAZ Kazakhstan KOR Korea, South KUW Kuwait LAT Latvia LIT Lithuania LUX Luxembourg MCD Macedonia MEX Mexico MON Mongolia MOR Morocco NET Netherlands NOR Norway NZL New Zealand PHI Philippines POL Poland POR Portugal PRK Korea, North PUR Puerto Rico ROM Romania RUS Russia SAF South Africa SIN Singapore SLO Slovenia SMN Serbia and Montenegro SPA Spain SWE Sweden THA Thailand TUN Tunisia TUR Turkey TWN Taiwan UKR Ukraine USA United States USS Soviet Union UZB Uzbekistan VIE Vietnam YUG Yugoslavia

References

  1. M. Aassila, 300 D´efis Math´ematiques, Ellipses, 2001.
  2. M. Aigner, G.M. Ziegler, Proofs from THE BOOK, Springer; 3rd edition, 2003.
  3. G.L. Alexanderson, L.F. Klosinski, L.C. Larson, The William Lowell Putnam Mathematical Competition, Problems and Solutions: 1965-1984, The Mathemat- ical Association of America, 1985.
  4. T. Andreescu, D. Andrica, 360 Problems for Mathematical Contests, GIL Pub- lishing House, Zal˘au, 2003.
  5. T. Andreescu, D. Andrica, An Introduction to the Diophantine Equations, GIL Publishing House, 2002.
  6. T. Andreescu, D. Andrica, Complex Numbers from A to ... Z, Birkh¨auser, Boston, 2005.
  7. T. Andreescu, B. Enescu, Mathematical Treasures, Birkh¨auser, Boston, 2003.
  8. T. Andreescu, Z. Feng, 102 Combinatorial Problems, Birkh¨auser Boston, 2002.
  9. T. Andreescu, Z. Feng, 103 Trigonometry Problems: From the Training of the USA IMO Team, Birkh¨auser Boston, 2004.
  10. T. Andreescu, Z. Feng, Mathematical Olympiads 1998-1999, Problems and Solu- tions from Around the World, The Mathematical Association of America, 2000.
  11. T. Andreescu, Z. Feng, Mathematical Olympiads 1999-2000, Problems and Solu- tions from Around the World, The Mathematical Association of America, 2002.
  12. T. Andreescu, Z. Feng, Mathematical Olympiads 2000-2001, Problems and Solu- tions from Around the World, The Mathematical Association of America, 2003.
  13. T. Andreescu, R. Gelca, Mathematical Olympiad Challenges, Birkh¨auser, Bos- ton, 2000.
  14. T. Andreescu, K. Kedlaya, Mathematical Contests 1996-1997, Olympiads Prob- lems and Solutions from Around the World, American Mathematics Competi- tions, 1998.
  15. T. Andreescu, K. Kedlaya, Mathematical Contests 1997-1998, Olympiads Prob- lems and Solutions from Around the World, American Mathematics Competi- tions, 1999.
  16. T. Andreescu, V. Cartoaje, G. Dospinescu, M. Lascu, Old and New Inequalities, GIL Publishing House, 2004.
  17. M. Arsenovi´c, V. Dragovi´c, Functional Equations (in Serbian), Mathematical Society of Serbia, Beograd, 1999.

References 18. M. Aˇsi´c et al., International Mathematical Olympiads (in Serbian), Mathemat- ical Society of Serbia, Beograd, 1986. 19. M. Aˇsi´c et al., 60 Problems for XIX IMO (in Serbian), Society of Mathemati- cians, Physicists, and Astronomers, Beograd, 1979. 20. A. Baker, A Concise Introduction to the Theory of Numbers, Cambridge Uni- versity Press, Cambridge, 1984. 21. E.J. Barbeau, Polynomials, Springer, 2003. 22. E.J. Barbeau, M.S. Klamkin, W.O.J. Moser, Five Hundred Mathematical Chal- lenges, The Mathematical Association of America, 1995. 23. E.J. Barbeau, Pell’s Equation, Springer-Verlag, 2003. 24. M. Becheanu, International Mathematical Olympiads 1959-2000. Problems. So- lutions. Results, Academic Distribution Center, Freeland, USA, 2001. 25. E.L. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for Your Mathematical Plays, AK Peters, Ltd., 2nd edition, 2001. 26. G. Berzsenyi, S.B. Maurer, The Contest Problem Book V, The Mathematical Association of America, 1997. 27. P.S. Bullen, D.S. Mitrinovi´c , M. Vasi´c, Means and Their Inequalities, Springer, 1989. 28. H.S.M. Coxeter, Introduction to Geometry, John Willey & Sons, New York, 1969 29. H.S.M. Coxeter, S.L. Greitzer, Geometry Revisited, Random House, New York, 1967. 30. I. Cuculescu, International Mathematical Olympiads for Students (in Roma- nian), Editura Tehnica, Bucharest, 1984.