IMO 1996 SL N3

Origin: BUL | Category: Number Theory

Problem

A finite sequence of integers $a_0, a_1, \ldots, a_n$ is called quadratic if for each $i \in {1, 2, \ldots, n}$ we have the equality $|a_i - a_{i-1}| = i^2$.

(a) Prove that for any two integers $b$ and $c$, there exist a natural number $n$ and a quadratic sequence with $a_0 = b$ and $a_n = c$.

(b) Find the smallest natural number $n$ for which there exists a quadratic sequence with $a_0 = 0$ and $a_n = 1996$.

Solution

(a) It clearly suffices to show that for every integer $c$ there exists a quadratic sequence with $a_0 = 0$ and $a_n = c$, i.e., that $c$ can be expressed as $\pm 1^2 \pm 2^2 \pm \cdots \pm n^2$. Since

$(n + 1)^2 - (n + 2)^2 - (n + 3)^2 + (n + 4)^2 = 4,$

we observe that if our claim is true for $c$, then it is also true for $c \pm 4$. Thus it remains only to prove the claim for $c = 0, 1, 2, 3$. But one immediately finds $1 = 1^2$, $2 = -1^2 - 2^2 - 3^2 + 4^2$, and $3 = -1^2 + 2^2$, while the case $c = 0$ is trivial.

(b) We have $a_0 = 0$ and $a_n = 1996$. Since

$a_n \leq 1^2 + 2^2 + \cdots + n^2 = \frac{1}{6} n(n + 1)(2n + 1),$

we get $a_{17} \leq 1785$, so $n \geq 18$. On the other hand, $a_{18}$ is of the same parity as

$1^2 + 2^2 + \cdots + 18^2 = 2109,$

so it cannot be equal to $1996$. Therefore we must have $n \geq 19$. To construct a required sequence with $n = 19$, we note that

$1^2 + 2^2 + \cdots + 19^2 = 2470 = 1996 + 2 \cdot 237;$

hence it is enough to write $237$ as a sum of distinct squares. Since

$237 = 14^2 + 5^2 + 4^2,$

we finally obtain

$1996 = 1^2 + 2^2 + 3^2 - 4^2 - 5^2 + 6^2 + \cdots + 13^2 - 14^2 + 15^2 + \cdots + 19^2.$