6. Find the smallest natural number $n$ such that for any coloring of the numbers 1, 2, 3, ..., $n$ with three colors, there exist two numbers of the same color whose difference is a square of a natural number.

(Vojtech Bálint, Michal Rolínek, Josef Tkadlec)
Solution. We will show that the sought natural number is $n=29$. First, we will show that no matter how we color the first 29 natural numbers, there will always be two numbers of the same color that differ by a square of a natural number. Then, we will provide an example of a suitable coloring of 28 numbers, which will show that no $n \leqq 28$ has the required property.

Assume, on the contrary, that the first 29 natural numbers can be colored with three colors $A$, $B$, and $C$ such that the difference of any two numbers of the same color is not a square, and let $f(i)$ denote the color of the number $i$ for $i \in\{1,2, \ldots, 29\}$.

Since 9, 16, and 25 are squares, each pair of the numbers 1, 10, 26 must have different colors. The same applies to each pair of the numbers $1, 17, 26$, so the numbers 10 and 17 must have the same color. The same reasoning can be applied to other triples of the form $a, a+9, a+25$ and $a, a+16, a+25$, $a \in\{2,3,4\}$, so the numbers 11 and 18, 12 and 19, 13 and 20 must also have the same color, i.e., $f(11)=f(18), f(12)=f(19)$, and $f(13)=f(20)$.

Let $A$ be the color of the numbers 10 and 17, i.e., $f(10)=f(17)=A$. Since the numbers 10 and 11 differ by $1=1^{2}$, the pair 11, 18 must have a different color than $A$, let's denote their color as $B$. Since $19=18+1^{2}=10+3^{2}$, $f(19)$ must be different from both $f(18)=B$ and $f(10)=A$, so $f(12)=f(19)=C$. From the equalities $20=19+1^{2}=11+3^{2}$, it similarly follows that $f(20) \neq f(19)=C$ and $f(20) \neq f(11)=B$, so $f(13)=f(20)=A$. We have derived $f(13)=A=f(17)$, which is the desired contradiction, since $17-13=4=2^{2}$. Therefore, such a coloring does not exist for the first 29 numbers.

A counterexample for $n=28$ is provided in the following table.

|  | ${ }^{1} B$ | ${ }^{2} \mathrm{C}$ | ${ }^{3} A$ |  |
| :---: | :---: | :---: | :---: | :---: |
| ${ }^{5} A$ | ${ }^{6} \mathrm{~B}$ | 7 | ${ }^{8} B$ |  |
| 10  $A$ | ${ }^{11} B$ | 12 | ${ }^{13}$ |  |
| ${ }^{15} A$ | ${ }^{16} B$ | 17  $A$ | ${ }^{18} B$ |  |
| ${ }^{20} A$ | ${ }^{21} B$ | ${ }^{22} A$ | ${ }^{23}$ |  |
| ${ }^{25} A$ | 26 | 27  $A$ | ${ }^{28} B$ |  |

Fig. 7

It is easy to verify that any two numbers that differ by $1, 4, 9, 16$, or 25 are colored differently.