Painting the plane, and finding points one unit apart

Question

An old (rather easy) contest problem reads as follows:

Each point in a plane is painted one of two colors. Prove that there exist two points exactly one unit apart that are the same color.

This proof can be easily written by constructing an equilateral triangle of side length $1$ unit and asserting that it is impossible for the colors of all three vertices to be pairwise unequal.

However, I was curious about the trickier problem

Each point in a plane is painted one of three colors. Do there exist two points exactly one unit apart that are the same color?

...now, if this happened in $3$-space, I could construct a tetrahedron... but I can't do this in $2$-space. Does this not work with three colors, or is the proof just more complicated? If it doesn't work, how can I construct a counterexample?

Answer 1

We can prove this by finding a more complicated set of points that cannot be colored. One example is known as the Moser spindle:

(The lines mark points that are one unit apart.)

Suppose we try to color these seven points with three colors. Color the point $4$ at the top of the diagram one of them - say, red. Then $3$ and $6$ have to be different both from $4$ and from each other. If we color them blue and green, then $2$ cannot be blue or green, so $2$ has to be red again: same as $4$.

Similarly, we can show that $1$ has to be the same color as $4$. But $1$ and $2$ are also exactly one unit apart, so they must be different colors! Therefore we can't color these seven points (and definitely can't color $\mathbb R^2$) with three colors, without giving two points one unit apart the same color.

Answer 2

This is the subject well-known open problem called the Hadwiger-Nelson Problem. The problem asks for the exact minimum number of colors that we can color the plane with, so that no two points of distance one are the same color.

You have observed that we cannot do it with only 2 colors, and asked, can we do it with 3 colors? The answer to that is no as well: on the Wikipedia page, we see that this is proven with the Mosser Spindle. It is a collection of 7 points in the plane, with 11 edges of length 1 between them, such that these points cannot be colored with only 3 colors.

Therefore it is known that 2 or 3 colors are impossible. It is not known, however, if it can be done with 4 colors. It is known that it can be done in 7 colors, so the minimum number of colors is either 4, 5, 6, or 7 -- but we don't know which!

In fact, it is expected by some that the exact minimum depends on the infamous Axiom of Choice.

UPDATE: Remarkable news earlier this year in April 2018: amateur mathematician Aubrey de Grey showed that 4 colors is impossible, thus narrowing the minimum down to 5, 6, or 7. To do this, he constructed a set of about 1500 points in the plane and proved that it is impossible to color them with 4 colors. This is the first progress on the problem in 60 years. You can read about it in de Grey's paper (which is quite readable). You can also read about it in this blog post and this Quanta magazine article.