67th Czech and Slovak Mathematical Olympiad

The answer is $n=29$.

First, for the sake of contradiction, assume that numbers $1,2,\dots ,29$ can be colored by colors $A,B,C$ such that no two numbers with the same color differ by a square. Let $f(i)$ be the color of number $i$ for $i\in \{1,2,\dots ,29\}$.

Since $9,16$, and $25$ are squares, numbers $1,10,26$ are all assigned distinct colors. The same is true for numbers $1,17,26$, hence $10$ and $17$ are assigned the same color. Likewise we get $f(11)=f(18)$, $f(12)=f(19)$ and $f(13)=f(20)$ (for the last equality we look at numbers $4,13,20,29$).

Without loss of generality, assume $f(10)=f(17)=A$. As $11=10+1^2$, we have $f(11)\ne f(10)$. Without loss of generality, let $f(11)=f(18)=B$. Now $19=18+1^2=10+3^2$, hence $f(12)=f(19)=C$. Similarly, $20=19+1^2=11+3^2$ implies $f(13)=f(20)=A$. We have derived $f(13)=A=f(17)$, a contradiction.

On the other hand, if $n\le 28$, we may color the numbers as below. It's easy to check that no two numbers with the same color differ by a square of an integer.



Fig. 4