Communications of the ACM
Home/Magazine Archive/November 2011 (Vol. 54, No. 11)/Puzzled: Distances Between Points on the Plane/Full Text
Last byte
Puzzled: Distances Between Points on the Plane
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.
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.)
Footnotes
Meanwhile, all readers are encouraged to submit prospective puzzles for future columns to [email protected].
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.
©2011 ACM 0001-0782/11/1100 $10.00
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.
No entries found