Two numbers whose difference is a full square are called friendly numbers. For example, the numbers $25$ and $16$ are friendly because their difference is $9$ full squares. Find the smallest natural number $n$ so that when we randomly paint the numbers $1, 2, 3, ..., n$ in three different colors, there are two friendly numbers of the same color.
I could not solve this question
On
We'll try to prevent friends being monochromatic, and see how big $n$ has to be to force a contradiction. Adjacent numbers are friendly, so say $1$ is red, $2$ is blue and the third colour is green. A computer-aided search finds the longest solutions have $n=28$, e.g. $rbgrbgrgrbgrgrbgbgrbgrbrbgrb$.
For $1\le i\le n-25$, the values $i,\,i+9,\,i+25$ must permute the colours, while $i+4,\,i+16$ must each differ in colour from $i$, and have the same colours as $i+25,\,i+9$ respectively. So $i,\,i+1,\,i+4,\,i+9,\,i+16,\,i+25$ have colours of the form $xyyzzy$ or $xyzyyz$. But $1$ to $4$ have possible colorations $rbgb,\,rbgr,\,rbrb,\,rbrg$. For example, the $n=28$ example above actually matches $rbgr$ and $xyyzzy$ for each of $i\in\{1,\,2,\,3\}$. A hypothetical $n=29$ solution is specified by which of $4\times2^4=64$ options it chooses for its start and the adding-squares patterns on $i\le4$, and presumably we can refute them in turn.
For $1\le k\le n-25$, numbers $k+9,k+16$ must have a different colour than $k$ and also different than $k+25$ and also $k, k+25$ must differ. We conclude that $k+9,k+16$ have same colour.. Then $k+8$ differs from $k+9$, $k+7$ differs from both $k+8$ and $k+16~k+9$, i.e. the three consecutive numbers $k+7,k+8,k+9$ use the three colours. If $n\ge33$, this holds for $k=1,2,\ldots,8$, so that numbers $8,9,\ldots,17$ cycle through the colours. In particular, $8$ and $17$ have sisme colour - contradiction! Can you solve the puzzle with $n=32$?