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

  • $\begingroup$ Is the question: Find $d$? Prove such a $d$ exists? Prove the statement is true for all $d$? Something else? $\endgroup$
    – Henry
    Mar 29 '11 at 0:30
  • $\begingroup$ @Henry: The statement should be true for all values of $d$. $\endgroup$ Mar 29 '11 at 0:38
  • $\begingroup$ Any other solutions that springs to mind? $\endgroup$ Mar 29 '11 at 0:39
  • 1
    $\begingroup$ 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. $\endgroup$ 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.

  • $\begingroup$ @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? $\endgroup$ Mar 29 '11 at 0:38
  • $\begingroup$ @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. $\endgroup$ Jun 23 '20 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.