How do I solve Problem 1 of the International Olympiad of Metropolis?

Question

The question is: Find all $n$ so that there exists $n$ consecutive numbers whose sum is a square!

My method to solve the problem: I would try to look at the values modulo $n$, and there I see there is no possible square for $n=2x>2$, so all even numbers bigger than 2, and that all odd numbers work...

I can also see that the sum of the consecutive numbers is $$\dfrac{((x+1)+(x+n)) \cdot n}{2}$$ So that has to give a square...

But how do I do that? I cannot put my method in application... Am I totally wrong, and I shouldn't do it like that?

Answer 1

As you noted in the question, if $x +1$ is the first number in the sum, then the sum of the $n$ consecutive numbers is $$ \frac{n}{2} \cdot (x + 1 + x + n). $$

If $n$ is odd, let $n = 2k + 1$, and take $x = k$. Then the sum of the $n$ consecutive numbers $(k + 1), (k + 2), \dots, (k + n)$ is $$ \frac{2k+1}{2} \cdot (k + 1 + k + 2k + 1) = (2k + 1)^2 $$ which is a square, so all odd numbers work.

Now suppose that $n$ is even. Let $n = 2k$ for some $k$.

Then the sum is equal to $$ k(2x + 2k + 1) $$.

The term in brackets is odd, so for this to be a square, the largest power of $2$ which divides $k$ must be even. i.e. We must have that $k = 2^{2m} \cdot d$ where $m$ is some natural number, and $d$ is an odd natural number.

The sum then reduces to $$ 2^{2m} \cdot d \cdot (2x + 2^{2m + 1} \cdot d + 1) $$

This is a square if and only if $$ d \cdot (2x + 2^{2m + 1} \cdot d + 1) $$ is a square, so it is enough to choose $x$ so that the term in brackets is a square multiple of $d$. That is, we try to choose $x$ so that $$ 2x + 2^{2m + 1} \cdot d + 1 = a^2 \cdot d $$ for some natural number $a$.

This is equivalent to $$ 2x + 1 = \left( a^2 - 2^{2m + 1} \right) \cdot d $$ and it is easy to see that this has a solution for x as long as $a$ is an odd square greater than $2^{2m + 1}$. Thus we have a solution in this case since there are arbitrarily large odd square numbers.

We see that if $n$ is even, then $n$ works if and only if $n$ is divisible by $2$ an odd number of times.

Answer 2

As noted in the statement of the question, the sum of $n$ consecutive numbers starting from $x+1$ is given by $$\sum_{j=x+1}^{x+n}j=\frac{(2x+1+n)n}{2}.$$ If $n=2m+1$ is an odd integer, then we require $$(x+m+1)(2m+1) = k^2$$ for some integer $k$. Clearly taking $x=m$ will yield a solution (as also noted by Win Vineeth). In fact, there are infinitely many solutions simply by solving for $x$, giving $$x = \frac{k^2}{n} - (m+1).$$ Then every $k$ such that $n\mid k^2$ will yield a distinct solution $x$, and conversely, these yield all the valid solutions.

On the other hand, if $n=2m$ is an even integer, then we require $$(2x+2m+1)m=k^2.$$ Let $2^s$ be the largest power of $2$ which divides $m$. Then writing $m=2^sm'$ where $m'$ is odd, we have $$(2x+2^{s+1}m'+1)2^sm'=k^2.$$ It follows that $s$ must be even, so that if $n$ is even, it must contain an odd number of $2$s in its factorization. Writing $k^2 = 2^sk'^2$ where $k'$ is odd, we then get $$(2x+2^{s+1}m'+1)m'=k'^2.$$ Then again there are an infinite family of solutions $$x=\frac{k'^2-m'}{2}-2^{s}m',$$ where every odd $k'$ will yield a distinct solution. Again, these yield all valid solutions.

In summary, there is a solution for $n$ if and only if $n$ is odd or if $n$ is even with an odd number of $2$s in its prime factorization. When there is a solution, there are infinitely many solutions.

Answer 3

All numbers other than odd multiples of $2^m$, where m is even.

Sum of n terms will be $ n/2 * ((2*x)+(n-1)) $

When m is even, the denominator is cancelled and 2 will be again raised to odd power in numerator and term in brackets will be odd number.

So you cannot have such n.

Answer 4

For any odd $n$, sum of $n$ consecutive numbers starting from $\frac {n+1}2$ is

$$\frac n2 (n+1+(n-1)*1) = n^2$$

Thus for every odd $n$, there exist $n$ consecutive numbers whose sum is a perfect square.

More details - This becomes simpler if you know Arithematic Progression. The formula for sum of $n$ numbers starting from $a$, which are $d$ apart (difference between successive numbers is $d$) is

$$S_n=\frac n2(2a+(n-1)d)$$

Here $d=1$ and $a$ can be calculated to be $\frac {n+1}2$

Thank you @Litho for pointing it out.