in every coloring $1,...,n$ there are distinct integers $a,b,c,d$ such that $a+b+c=d$

Question

Prove that for every $k$ there is a finite integer $n = n(k)$ so that for any coloring of the integers $1, 2, . . . , n$ by $k$ colors there are distinct integers $a, b, c$ and $d$ of the same color satisfying $a + b + c = d$

Answer 1

By Ramsey's theorem we can choose $n=n(k)$ so that, for any coloring of the $2$-element subsets of an $n+1$-element set with $k$ colors, there is a $7$-element subset whose $2$-element subsets all have the same color.

Now suppose the numbers $1,2,\dots,n$ are colored with $k$ colors. Color the $2$-element subsets of the set $\{0,1,2,\dots,n\}$ as follows: if $x,y\in\{0,1,2,\dots,n\}$ and $x\lt y$, give $\{x,y\}$ the same color as the number $y-x$. Thus there are numbers $x_1\lt x_2\lt x_3\lt x_4\lt x_5\lt x_6\lt x_7$ such that all the differences $x_j-x_i\ (1\le i\lt j\le7)$ have the same color.

Choose $i\in\{3,4\}$ so that $x_i-x_2\ne x_2-x_1$ and then choose $j\in\{5,6,7\}$ so that $x_j-x_i\ne x_2-x_1,\ x_i-x_2$.

Let $a=x_2-x_1,\ b=x_i-x_2,\ c=x_j-x_i$ and $d=x_j-x_1$. Then $a,\ b,\ c,\ d$ are distinct, and $a,\ b,\ c,\ a+b,\ b+c$, and $a+b+c=d$ all have the same color.

Alternatively choose $m=m(k)$ so that, for any coloring of the $2$-element subsets of an $m+1$-element set with $k$ colors, there is a $4$-element subset whose $2$-element subsets all have the same color, and let $n=n(k)=2^m-1$.

Now suppose the numbers $1,2,\dots,n$ are colored with $k$ colors. Color the $2$-element subsets of the set $\{0,1,\dots,m\}$ as follows: if $x,y\in\{0,1,\dots,m\}$ and $x\lt y$, give $\{x,y\}$ the same color as the number $2^y-2^x$. Thus there are numbers $x_1\lt x_2\lt x_3\lt x_4$ such that all the differences $2^{x_j}-2^{x_i}(1\le i\lt j\le4)$ have the same color.

Let $a=2^{x_2}-2^{x_1},\ b=2^{x_3}-2^{x_2},\ c=2^{x_4}-2^{x_3},\ d=2^{x_4}-2^{x_1}$. Then $a\lt b\lt c\lt d$ and $a,\ b,\ c,\ a+b,\ b+c$, and $a+b+c=d$ all have the same color.

This construction can be improved by using a Sidon sequence (also called a Golomb ruler) $a_0,a_1,\dots,a_m$ instead of $2^0,2^1,\dots,2^m.$