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

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.

Answer 2

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 3

You can alternatively construct two equilateral triangles ABC and BDC with side length 1 unit, such that they share the basis BC (see image).

Now consider the three sets G, R, and Y, where G contains all the green points, R all the red points and Y all the yellow points (these are the three colors I've used). Let w.l.o.g. A $\in$ G. If B $\in$ G or C $\in$ G, we are done with the proof. We will assume therefore that B $\notin$ G and C $\notin$ G. Now if B and C have the same color, we would be also done with the proof, so we'll assume w.l.o.g. that B $\in$ R and C $\in$ Y.

Again, if D $\in$ R or D $\in$ Y, we could complete our prove, because one of the 1-unit-segments BD and CD would connect two points with the same color, so we'll let D $\in$ G.

Construct now a circle centered at A (colored green) with radius $\sqrt{3}$. Since the altitude of an equilateral triangle with side 1 is $\frac{\sqrt{3}}{2}$, point D would lie on the circumference. Move now the point D (colored green too) around the circumference, preserving the two-equilateral-triangles-construction.

Note, that if any point P lying on the circumference is colored red or yellow, either the one unit segment PB or PC would join two points with the same color, one unit apart, and we could conclude our proof, so we'll let all points lying on the circumference be colored green. With this configuration, you can find a one unit chord connecting two points on the circumference colored green (do you see why?).

Q.E.D

PS: Sorry for my spelling and grammar mistakes. How can I attach the images correctly?