IMO 2000 SL N6

Origin: ROM | Category: Number Theory

Problem

Show that the set of positive integers that cannot be repre- sented as a sum of distinct perfect squares is finite.

Solution

Suppose that a natural number N satisfies N = a2 1 + \cdot \cdot \cdot + a2 k, 2N = b2 1 +\cdot \cdot \cdot+b2 l , where ai, bj are natural numbers such that none of the ratios ai/aj, bi/bj, ai/bj, bj/ai is a power of 2. We claim that every natural number n > 4N−2 i=0 (2iN + 1)2 can be rep- resented as a sum of distinct squares. Suppose n = 4qN + r, 0 \leqr < 4N. Then n = 4Ns + r−1  i=0 (2iN + 1)2 for some positive integer s, so it is enough to show that 4Ns is a sum of distinct even squares. Let s = C c=1 22uc + D d=1 22vd+1 be the binary expansion of s. Then 4Ns = C  c=1 k  i=1 (2uc+1ai)2 + D  d=1 l  j=1 (2ud+1bj)2, where all the summands are distinct by the condition on ai, bj.

It remains to choose an appropriate N: for example N = 29, because 29 = 52 + 22 and 58 = 72 + 32. Second solution. It can be directly checked that every odd integer 67 < n \leq211 can be represented as a sum of distinct squares. For any n > 211 we can choose an integer m such that m2 > n 2 and n −m2 is odd and greater than 67, and therefore by the induction hypothesis can be written as a sum of distinct squares. Hence n is also a sum of distinct squares.