[Math] Painting the plane, and finding points one unit apart

contest-mathcoordinate systemsgeometrygraph theory

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?

Best Answer

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.

Related Question