Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
Is the question: Find $d$? Prove such a $d$ exists? Prove the statement is true for all $d$? Something else? –  Henry Mar 29 '11 at 0:30
@Henry: The statement should be true for all values of $d$. –  David Kohler Mar 29 '11 at 0:38
Any other solutions that springs to mind? –  David Kohler 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. –  André Nicolas Mar 29 '11 at 0:51
add comment

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
@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? –  David Kohler Mar 29 '11 at 0:38
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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