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$$

• Is the question: Find $d$? Prove such a $d$ exists? Prove the statement is true for all $d$? Something else? Mar 29 '11 at 0:30
• @Henry: The statement should be true for all values of $d$. Mar 29 '11 at 0:38
• Any other solutions that springs to mind? Mar 29 '11 at 0:39
• Something independent of $k$ would obviously be useful. Lots of things with the same basic structure are, by linearity. This one (the second difference) is the simplest. Mar 29 '11 at 0:51

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.

• @user6312 Thanks for your answer. A question: How did you notice the identity summing up to $4d^2$? I'm trying to see how to explain that very important first step to a student who is training for the competition and to me, it seems hard to come up with a general approach. Any suggestions? Mar 29 '11 at 0:38
• @DavidKohler I came across the problem you posted last year on another site, and found the same identity. My motivation comes from this problem: Prove there exists disjoint sets of integers such that the sum of $k$th powers for $k \le n$ in each set is equal. If the sum and sum of squares is equal, perhaps we can get the $k$ and $k^2$ terms to cancel. It turns out I didn't need equal sum of squares at all. For $A=\{0,3\}, B=\{2, 1\},$ we have $|A|=|B|, 0+3=2+1,$ which is enough to see that the $d$ and $1$ term in $1^2 - (1+d)^2 - (1+2d)^2 + (1+3d)^2$ cancel. Then attach a $k$ and you're done. Jun 23 '20 at 1:37