I have a problem from my sister's studies: Find the minimum number $n$ such that, for every partition of the set $X=\{1,2,...,n\}$ into three non-empty subsets, there always exist two numbers $a$ and $b$ in the same subset with $|a-b|$ a square number.
I'm a bit not good of this kind of math, thank for your help.
This is really a graph theory question. Given $n$, let $G(n)$ be the graph with vertices $1$ to $n$ and edges $(i, i+k^2)$ for positive integers $k$ such that $i+k^2 \le n$.
What is the smallest $n$ such that the chromatic number of $G(n)$ is greater than $3$.
I don't know if there's an easy way to do it by hand, but using Maple I find the answer is $29$.
Here's a picture of the case $n=28$ with vertices coloured red, green, blue corresponding to a partition where $|a-b|$ for $a$ and $b$ in the same subset is never a square.