IMO Problem Shortlist

Define a function $f$ on the set of positive integers by $f(n)=0$ if $n$ is balanced and $f(n)=1$ otherwise. Clearly, $f(nm)\equiv f(n)+f(m)\mathrm{mod}2$ for all positive integers $n,m$.

a. Now for each positive integer $n$ consider the binary sequence $(f(n+1),f(n+2),\dots ,f(n+50))$. As there are only $2^{50}$ different such sequences there are two different positive integers $a$ and $b$ such that $$(f(a+1),f(a+2),\dots ,f(a+50))=(f(b+1),f(b+2),\dots ,f(b+50)).$$ But this implies that for the polynomial $P(x)=(x+a)(x+b)$ all the numbers $P(1),P(2),\dots ,P(50)$ are balanced, since for all $1\le k\le 50$ we have $f(P(k))\equiv f(a+k)+f(b+k)\equiv 2f(a+k)\equiv 0\mathrm{mod}2$.

b. Now suppose $P(n)$ is balanced for all positive integers $n$ and $a<b$. Set $n=k(b-a)-a$ for sufficiently large $k$, such that $n$ is positive. Then $P(n)=k(k+1)(b-a{)}^2$, and this number can only be balanced, if $f(k)=f(k+1)$ holds. Thus, the sequence $f(k)$ must become constant for sufficiently large $k$. But this is not possible, as for every prime $p$ we have $f(p)=1$ and for every square $t^2$ we have $f\left(t^2\right)=0$. Hence $a=b$.