Determine the least positive integer $n$ with the following property – for every 3-coloring of numbers $1,2,\ldots,n$ there are two (different) numbers $a,b$ of the same color such that $|a-b|$ is a perfect square.
Problem
Source: Czech and Slovak Olympiad 2018, National Round, Problem 6
Tags: Combinatorial Number Theory, national olympiad, combinatorics, number theory
15.08.2018 12:01
Any idea?
18.08.2018 11:23
In my tradition, let the set of numbers be $0,1,\ldots,n-1$ Let the set of numbers with the same color be $A,B,C$. For $n=28$, we have \begin{align*} A & =\left\{ 0,3,6,8,11,13,18,21,23,26\right\} \\ B & =\left\{ 1,4,9,14,16,19,22,24,27\right\} \\ C & =\left\{ 2,5,7,10,12,15,17,20,25\right\} . \end{align*}We show that $n=29$ is impossible. Since $3^{2}+4^{2}=5^{2}$, the following must belong to different group$\left(\heartsuit\right)$ \begin{align*} \left\{ 0\right\} ,\left\{ 9,16\right\} ,\left\{ 25\right\} \\ \left\{ 1\right\} ,\left\{ 10,17\right\} ,\left\{ 26\right\} \\ \left\{ 2\right\} ,\left\{ 11,18\right\} ,\left\{ 27\right\} \\ \left\{ 3\right\} ,\left\{ 12,19\right\} ,\left\{ 28\right\} \end{align*}WLOG, we may assume $0\in A$ and $9,16\in B$ and $25\in C$. There are 2 possibility for set of 1. For the case $1\in B$, since $25\in C$, we must have $26\in A$ and $10,17\in C$. Then, since $9\in B$ and $17\in C$, we have $18\in A$. Then, from $\left(\heartsuit\right)$ and $1\in B$ ,$26\in A$, we have $2\in C$ and $27\in B$ and $11\in A$. Then, since $11\in A$, $16\in B$, we must have $12\in C$ implies $19\in C$. But we have $10\in C$, a contradiction. For the case $1\in C$, since $25\in C,9\in B$, we must have $10,17\in A$ and $26\in B$. Then, since $17\in A$ and $9\in B$, we have $18,8\in C$. Moreover, since $18\in C$ and $9\in B$, we have $27\in A$ and $2\in B$. Then, since $16\in B$ and $8\in C$, we have $12,19\in A$. But we have $10\in A$, a contradiction. Therefore the largest $n$ is 28.
18.08.2018 11:28
Nice......
02.07.2024 21:10
soryn wrote: Any idea? official solution: https://www.matematickaolympiada.cz/media/3459612/brozura_a67angl_new.pdf#page=16