Czech and Slovak Mathematical Olympiad

The answer is $n = 29$.

First, for the sake of contradiction, assume that numbers $1, 2, \ldots, 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, \ldots, 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) \neq 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