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?

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.

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

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.

  • Wow, awesome! I know you already answered my question, but do you know if there is one of these for $4$ colors? – Frpzzd Oct 10 '17 at 23:43
  • 4
    @Nilknarf If you prove 4 colors are impossible, then you would be solving a famous open problem :) I have tried to explain some in my answer. – 6005 Oct 10 '17 at 23:44
  • @6005 Oh, I see. Just found the Wikipedia page. :D – Frpzzd Oct 10 '17 at 23:45
  • 2
    @Frpzzd Funnily enough, your question is now answered that there is one of these for 4 colors: it has about 1500 points and was discovered earlier this year by Aubrey de Grey, a biologist and age researcher (and amateur mathematician). The result is the first progress on the problem in 60 years. – 6005 Aug 11 at 3:46

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

enter image description here

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.

enter image description here

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?

  • You seem to have rediscovered the Moser spindle construction explained in Misha Lavrov's answer. Your ABCD correspond to their 4362 and 4751. – Henning Makholm Oct 7 at 23:02
  • @HenningMakholm You're right, our configurations are indeed similar. And although the solution that Misha Lavrov proposed is more visual, I still think that it's easier or at least more likely to arrive at my solution when thinking about how to approach the problem... – Dr. Mathva Oct 8 at 17:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.