David Madore's WebLog: Seven colors

This image represents a periodic tiling of the plane with hexagons colored with seven colors, having plenty of nice mathematical properties. One of them is this: if you take any two points the distance between which is given by the little black rod shown on the upper left, then these two points cannot have the same color. In other words, no matter how you move the rod in the picture, so long as you don't change its size, the two ends will fall on different colors.

Can this be done with fewer than seven colors? In other words, is there a way to color the plane (not necessarily perodically) using six colors or less, in such a way that any two points separated by a certain distance d fixed a priori are always of different colors? Interestingly enough, the answer to this problem is not known: I believe this is still an open problem. (I don't know who asked the question in the first place. It sounds typical of Pál Erdős, but that's mere guessing.)

Probably this is the mathematical problem with the simplest formulation which is still open.

It can be shown, however, that no plane coloring with three or less colors can do the trick: if you color the plane, in any way whatsoever, using three colors or less, and you fix an arbitrary distance d, then there are always, somewhere, two points separated by that distance d that are of the same color. This is a very nice mathematical exercise, because it requires almost no knowledge of geometry (let alone of any other domain of mathematics), and yet it is not at all obvious—almost an exercise of pure reasoning. I remember hitting my head against the walls for quite some time before I found the trick; and I occasionally gave it to students to try, nearly driving some of them mad. The problem with two colors (showing that two colors or fewer cannot suffice to color the plane in such a way that two points at distance d are not of the same color), however, is very simple, and anyone should be able to solve that; and it holds the key to solving the case of three colors.

So I can't be held responsible for people banging their head against walls, I'll provide the answer to the two- and three-color problems now. (Click here to reveal the following text if it is invisible.) First, the two-color case: consider an equilateral triangle with side d anywhere in the plane; then each vertex of the triangle cannot be of the same color as any other vertex, and this means that there are at least three colors. Now the three-color case: suppose we have a coloring of the plane with three colors such that no two points at distance d are of the same color (and we want to reach a contradiction). Consider an equilateral triangle ABC of side d again: then certainly its three vertices must be of all three colors. So if we put another equilateral triangle side to side, say BCD, then the color of point D must be the same as the color of point A (since they share the edge BC: the color cannot be that of B nor that of C, and there are only three colors). So D has the same color as A, but this is true whenever the figure can be drawn, that is, whenever the distance between A and D is that of two equilateral triangles of side d sharing a common side (this means the distance between A and D is sqrt(3)·d but that's unimportant). If we draw the entire circle of center A having that distance as radius, then all points on that circle are supposed to have the same color as A; and we can certainly find two points on that circle having distance d, a contradiction, which completes the proof.

Perhaps this is a nice test to determine whether a person is mathematically inclined, or could be, even if that person has no knowledge of mathematics: anyone so inclined will not resist thinking about such a simple and elegant problem for some time.

Update: The problem in question is known as the Hadwiger-Nelson problem: see this later entry (in French) and the ones linked from there.