CMO 2011 Sum of integers The following problem was asked in the CMO 2011 and I'd be interested in finding various solutions for it. Here's the problem:

Fix a positive integer $d$, then for any integer $k$ there exists a positive integer $n$ and integers $\epsilon_i$ where $\epsilon_i = \pm 1$ for $i=1 \ldots n$ such that:
$$k = \sum_{i=1}^n \epsilon_i (1+id)^2$$

 A: Let $U_k=(1+kd)^2$.  Then $U_{k+3}-U_{k+2} -U_{k+1}+U_k=4d^2$, a constant.  Changing signs, we obtain the sum $-4d^2$. 
Thus if we have found an expression for a certain number $S_0$ as a sum of the desired type, we can obtain an expression of the desired type for $S_0+(4d^2)q$, for any integer $q$.
It remains to show that for any $S$, there exists an integer $S'$ such that $S' \equiv S \pmod{4d^2}$ and $S'$ can be expressed in the desired form.
Look at the sum
$(1+d)^2+(1+2d)^2 +\cdots +(1+Nd)^2$, 
where $N$ is ``large.'' We can at will choose $N$ so that the sum is  odd, or so that the sum is even.
By changing the sign in front of $(1+kd)^2$ to a minus sign, we decrease the sum by $2(1+kd)^2$.  In particular, if $k \equiv 0 \pmod {2d}$, we decrease the sum by 2 (modulo $4d^2$).  If $N$ is large enough, there are many $k< N$ such that $k$ is a multiple of $2d$.  By switching the sign in front of $r$ of these, we change (``downward'') the congruence class modulo $4d^2$ by $2r$.  By choosing $N$ so that the original sum is odd, and choosing suitable $r <2d^2$, we can obtain numbers congruent to all odd numbers modulo $4d^2$.  By choosing $N$ so that the original sum is even, we can obtain numbers congruent to all even numbers modulo $4d^2$.  This completes the proof.
There is not much of a complication if instead of $1+kd$ we use $a+kd$, where $a$ and $d$ are relatively prime.
