Communications - November 2011

last;byte

DOI: 10.1145/2018396.2018422
Peter Winkler

Puzzled Distances Between Points on the Plane Welcome to three new puzzles. Solutions to the first two will be published next month; the third is as yet (famously) unsolved.

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.)