
6. Find the smallest positive integer $n$ such that for any coloring of numbers 1,2 , $3, \ldots, n$ by three colors there exist two numbers with the same color whose difference is a square of an integer. (Vojtech Bálint, Michal Rolínek, Josef Tkadlec)


Solution. 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)$ a $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 \leqslant 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.

|  |  |  |  |  |
| :---: | :---: | :---: | :---: | :---: |
|  | $B$ | $C$ | $A$ | $C$ |
| $A$ | ${ }^{6} B$ | $C$ | $B$ | ${ }^{9} C$ |
| 10 | 11 | 12 | 13 | 14 |
| $A$ | $B$ | $C$ | $B$ | $C$ |
| 15 | $16{ }_{D}$ | 17 |  | 19 |
| $A$ | $B$ | $A$ | $B$ | $C$ |
| ${ }^{20} A$ | ${ }^{21} B$ | ${ }^{22} A$ | ${ }^{23} B$ | ${ }^{24} C$ |
| ${ }^{25} A$ | ${ }^{26} C$ | ${ }^{27} A$ | ${ }^{28} B$ |  |

Fig. 4

## Results of the Final Round
