IMO 1992 SL 21

Origin: GBR

Problem

For each positive integer n, denote by s(n) the greatest integer such that for all positive integers k \leqs(n), n2 can be expressed as a sum of squares of k positive integers. (a) Prove that s(n) \leqn2 −14 for all n \geq4. (b) Find a number n such that s(n) = n2 −14. (c) Prove that there exist infinitely many positive integers n such that s(n) = n2 −14.

Solution

(a) Representing n2 as a sum of n2 −13 squares is equivalent to repre- senting 13 as a sum of numbers of the form x2 −1, x \inN, such as 0, 3, 8, 15, . . .. But it is easy to check that this is impossible, and hence s(n) \leqn2 −14. (b) Let us prove that s(13) = 132 −14 = 155. Observe that 132 = 82 + 82 + 42 + 42 + 32 = 82 + 82 + 42 + 42 + 22 + 22 + 12 = 82 + 82 + 42 + 32 + 32 + 22 + 12 + 12 + 12. Given any representation of n2 as a sum of m squares one of which is even, we can construct a representation as a sum of m + 3 squares by dividing the odd square into four equal squares. Thus the first equality enables us to construct representations with 5, 8, 11, . . ., 155 squares, the second to construct ones with 7, 10, 13, . . ., 154 squares, and the

third with 9, 12, . . ., 153 squares. It remains only to represent 132 as a sum of k = 2, 3, 4, 6 squares. This can be done as follows: 132 = 122 + 52 = 122 + 42 + 32 = 112 + 42 + 42 + 42 = 122 + 32 + 22 + 22 + 22 + 22. (c) We shall prove that whenever s(n) = n2 −14 for some n \geq13, it also holds that s(2n) = (2n)2 −14. This will imply that s(n) = n2 −14 for any n = 2t \cdot 13. If n2 = x2 1 + \cdot \cdot \cdot + x2 r, then we have (2n)2 = (2x1)2 + \cdot \cdot \cdot + (2xr)2. Replacing (2xi)2 with x2 i +x2 i +x2 i +x2 i as long as it is possible we can obtain representations of (2n)2 consisting of r, r + 3, . . . , 4r squares. This gives representations of (2n)2 into k squares for any k \leq4n2−62. Further, we observe that each number m \geq14 can be written as a sum of k \geqm numbers of the form x2 −1, x \inN, which is easy to verify. Therefore if k \leq4n2−14, it follows that 4n2−k is a sum of k numbers of the form x2 −1 (since k \geq4n2 −k \geq14), and consequently 4n2 is a sum of k squares. Remark. One can find exactly the value of f(n) for each n: f(n) = ⎧ ⎨ ⎩ 1, if n has a prime divisor congruent to 3 mod 4; 2, if n is of the form 5 \cdot 2k, k a positive integer; n2 −14, otherwise.