Maths Olympiad Prep

Library / /6 of 7

Number theory Difficulty 9.0 IMO level Prove it Netherlands

We call an integer n3n \ge 3 polypythagorean if there are nn distinct positive integers that you can put around a circle such that the sum of the squares of each pair of neighbouring numbers is a square. Thus, 33 is a polypythagorean integer because for example for the triple (44,117,240)(44, 117, 240), we have 442+1172=125244^2+117^2 = 125^2, 1172+2402=2672117^2 + 240^2 = 267^2 and 2402+442=2442240^2 + 44^2 = 244^2.
Find all polypythagorean integers.

Solution

We prove by induction that all integers greater than or equal to 22 are polypythagorean. Extend the definition of polypythagorean to n=2n = 2 in the logical way. For the induction basis, take (3,4)(3, 4) for n=2n = 2 and (44,117,240)(44, 117, 240) from the example for n=3n = 3.

For the induction step, let n4n \ge 4 and assume for our induction hypothesis that all 2k<n2 \le k < n are polypythagorean. In particular, n2n - 2 is polypythagorean.
Let (a1,a2,,an2)(a_1, a_2, \dots, a_{n-2}) be such that when put around a circle, the sum of squares of each pair of neighbouring integers is a square. Choose a prime number pp that does not divide any of the aia_i. Then let x=p21x = p^2 - 1 and y=2py = 2p so that x2+y2=(p21)2+(2p)2=(p2+1)2x^2 + y^2 = (p^2 - 1)^2 + (2p)^2 = (p^2 + 1)^2. By multiplying our n2n-2 integers by xx, we can now add two integers: (xa1,xa2,,xan2,yan2,ya1)(xa_1, xa_2, \dots, xa_{n-2}, ya_{n-2}, ya_1).

We simply check that
(xai)2+(xai+1)2=x2(ai2+ai+12)(xan2)2+(yan2)2=(x2+y2)an22(yan2)2+(ya1)2=y2(an22+a12)(ya1)2+(xa1)2=(y2+x2)a12 \begin{align*} (xa_i)^2 + (xa_{i+1})^2 &= x^2(a_i^2 + a_{i+1}^2) \\ (xa_{n-2})^2 + (ya_{n-2})^2 &= (x^2 + y^2)a_{n-2}^2 \\ (ya_{n-2})^2 + (ya_1)^2 &= y^2(a_{n-2}^2 + a_1^2) \\ (ya_1)^2 + (xa_1)^2 &= (y^2 + x^2)a_1^2 \end{align*}
and these are indeed all squares by the induction hypothesis and by construction of xx and yy. As the integers a1,a2,,an2a_1, a_2, \ldots, a_{n-2} are all different, the numbers xa1,xa2,,xan2xa_1, xa_2, \ldots, xa_{n-2} are also all different from each other. The numbers yan2ya_{n-2} and ya1ya_1 are also different from each other. As yy is divisible by pp, but xx and aia_i are not, neither yan2ya_{n-2} nor ya1ya_1 can be equal to any of the xaixa_i. We conclude that xa1,xa2,,xan2,yan2,ya1xa_1, xa_2, \ldots, xa_{n-2}, ya_{n-2}, ya_1 are all different, so nn is polypythagorean. This completes the induction.

\square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.