David Madore's WebLog: Seven colors

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

↓Entry #0166 [older| permalink|newer] / ↓Entrée #0166 [précédente| permalien|suivante] ↓


Seven colors

[Plane coloring]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.) 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.

↑Entry #0166 [older| permalink|newer] / ↑Entrée #0166 [précédente| permalien|suivante] ↑

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]