42nd Balkan Mathematical Olympiad

First, we will show that all numbers $n=4^m$ with $m\in {\mathbb{Z}}^{+}$ are not good. Indeed, consider the last sum in the given condition $$a_1+a_2+\cdots +a_n=1+2+\cdots +n=\frac{4^m(4^m+1)}{2}$$ Suppose that there exists $x\in \mathbb{Z}$ such that $$\frac{4^m(4^m+1)}{2}\equiv x^2(\mathrm{mod}{4}^m)⟺4^m\equiv 2x^2(\mathrm{mod}2\cdot 4^m)⟺2\cdot 4^m\mid 4^m-2x^2$$ This means that $4^m\mid 2x^2$, that is $2^{2m-1}\mid x^2$, so $2^m\mid x$. Let $x=c\cdot 2^m$ with $c\in \mathbb{Z}$. Thus $$4^m\equiv 2(2^{m}c{)}^2\equiv 2c^2\cdot 4^m\equiv 0(\mathrm{mod}2\cdot 4^m)$$ this implies that $4^m\equiv 0(\mathrm{mod}2\cdot 4^m)$, which is not true. This proves the second part of the problem, i.e. that there are infinitely many numbers that are not good.

Now let $n=p$ be a prime number of the form $4k+3,k\in \mathbb{Z}$. Consider the numbers $$1^2,2^2,\dots ,{\left(\frac{p-1}{2}\right)}^2,p-1^2,p-2^2,\dots ,p-{\left(\frac{p-1}{2}\right)}^2$$ Clearly, in this sequence, no two numbers are congruent modulo $p$. Indeed, suppose that there is $i^2\equiv j^2(\mathrm{mod}p)$ with $1\le i<j\le \frac{p-1}{2}$ then $p\mid (j-i)(j+i)$. But $0<j+i<p,0<j-i<p$, contradiction. From there, it follows that the first $\frac{p-1}{2}$ numbers have distinct remainders in modulo $p$. We reason similarly for the last $\frac{p-1}{2}$ numbers. Next suppose that there is $i^2\equiv p-j^2(\mathrm{mod}p)$ with $1\le i,j\le \frac{p-1}{2}$ then $p\mid i^2+j^2$. According to the well known properties of quadratic residues modulo a prime $p=4k+3$, we conclude that $p\mid i$ and $p\mid j$, which is also a contradiction. Thus, the claim is proved.

Notice that for $1\le i\le \frac{p-1}{2}$, two numbers $i^2$ and $p-i^2$ have different parity remainders in modulo $p$ (since the sum of the two remainders is $p$, which is odd). Consider the remainder of $1^2,2^2,\dots ,{\left(\frac{p-1}{2}\right)}^2$ when divided by $p$. We denote by $a_1,a_2,\dots ,a_m$ the odd remainders and by $b_1,b_2,\dots ,b_n$ the even remainders; note that $m+n=\frac{p-1}{2}$. Finally, consider the following permutation: $$a_1,p-a_1,a_2,p-a_2,\dots ,a_m,p-a_m,p,b_1,p-b_1,b_2,p-b_2,\dots ,b_n,p-b_n$$ Obviously, according to the above arguments, two consecutive numbers in the above permutation have different parity, and the sum of any first $i$ numbers in the permutation is either congruent to 0 or congruent to some number in $\{1^2,2^2,\dots ,{\left(\frac{p-1}{2}\right)}^2\}$, which is clearly a quadratic residue modulo $p$. Thus, the constructed permutation as above satisfies the given conditions. Since there are infinitely many primes of the form $p=4k+3$, we have proved that there are infinitely many good numbers as well.