Coloring $\mathbb R^n$ with $n$ colors always gives us a color with all distances.

I wanted to share a really cool but simple problem.

Consider a coloring of the points of $\mathbb R^n$ with $n$ colors. Prove that there is a color $c$ such that for any $r>0$ there are two points of the color $c$ at that distance.

Regards.

Solution 1:

It seems the following.

Assume the converse: for each color $i$ there exists a number $r_i>0$ such that there are no two points of the color $i$ at that distance. After a (re)enumeration we can assume $r_1\ge r_2\ge\dots r_n$. For each $i$ let $X_i$ be a set of points of $\Bbb R^n$ colored by color $i$.

Now we do the following inductive construction. Let $j_1=\min \{j:X_j\ne\varnothing\}$. Pick an arbitrary point $x_1\in X_{j_1}$. Let $S_1$ be a $(n-1)$-dimensional sphere with center $x_1$ and radius $R_1=r_{i_1}$. Then $S_1\subset\Bbb R^n\setminus X_{j_1}$. Suppose that $1\le i<n$ and for each $1\le l\le i$ we already build an $(n-l)$-dimensional sphere $S_l$ with radius $R_l\ge\frac {r_{j_l}}{\sqrt 2}$ and an index $j_l$ such that if $1<l\le i$ then $j_l=\min \{j: X_{j}\cap S_{l-1}\ne\varnothing\}$ and $S_l\subset S_{l-1}\setminus X_{j_l}$. Put $j_{i+1}=\min \{j: X_{j}\cap S_i\ne\varnothing\}$. Then $j_{i+1}>j_i$. Pick an arbitrary point $x_{i+1}\in X_{j_{i+1}}\cap S_i$. Then an intersection $$S_{i+1}=S_i \cap \{x\in\Bbb R^n: |x-x_{i+1}|=r_{j_{i+1}}\}\subset S_i \setminus X_{j_{i+1}}$$ is an $(n-i-1)$-dimensional sphere with radius $$R_{i+1}=r_{j_{i+1}}\sqrt{1-\left(\frac{r_{j_{i+1}}}{2R_i}\right)^2}.$$ From inequalities $r_{j_{i+1}}\le r_{j_{i}}$ and $R_i\ge\frac {r_{j_i}}{\sqrt 2}$ it follows that $R_{i+1}\ge\frac {r_{j_{i+1}}}{\sqrt 2}$.

At the end of the construction we obtain a zero-dimensional sphere $S_n$ (that is, a two-point set). But since the sequence $\{j_i\}$ is strictly increasing, we have $j_n=n,j_{n-1}=n-1,\dots, j_1=1$ and so $S_n\subset S_1\cap \bigcap_{i=2}^n S_{i-1}\setminus X_i \subset (\Bbb R^n\setminus X_{1})\cap \bigcap_{i=2}^n (\Bbb R^n\setminus X_i)=\varnothing$, a contradiction.