# Communications of the ACM

Last byte

## Puzzled: Distances Between Points on the Plane

The theme is distances between points on the plane. You might want a ruler and a large blank sheet of paper first...

1. It seems that in 1539, when Friar Marcos de Niza reported he had seen the fabled Seven Cities of Gold (in what is today New Mexico) he wasn't believed. According to my sources, he claimed the cities were located in such a way that among any three of them, at least two were exactly 10 leagues apart. Spanish officials claimed no such layout was possible on a flat surface. Were they right?

2. In more modern times, we would like to place nine equally strong Frisbee throwers in a field in such a way that no two of them are more than 100 yards apart, but as many pairs as possible are exactly that distance. How would you place them? Can you prove you can't do better?

3. You can use your solution to the first puzzle to show it will take at least four colors to paint the plane in such a way that no two points at unit distance get the same color. On the other hand, if you tile the plane with regular hexagons of the right size and paint them with seven colors in such a way that each hexagonal cell is surrounded by six cells of the other six colors, then you will have a way to paint the plane with seven colors such that no two points at unit distance get the same color (see the figure here).

So, four colors are necessary, and seven sufficient, to color the plane in such a way that no two points at distance 1 are the same color. What's the right number? (To learn much more about this problem, read The Mathematical Coloring Book by Alexander Soifer, Springer, 2009.)

### Author

Peter Winkler (puzzled@cacm.acm.org) is William Morrill Professor of Mathematics and Computer Science at Dartmouth College, Hanover, NH.

### Footnotes

Meanwhile, all readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

### Figures

Figure. Seven-coloring of the plane. If the hexagons' sides are of length a bit less than 1/2, no two points at distance 1 will have the same color.