acm-header
Sign In

Communications of the ACM

Last byte

Puzzled: Distances Between Points on the Plane


seven coloring of 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.)

Back to Top

Author

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

Back to Top

Footnotes

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

Back to Top

Figures

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

Back to top


©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 permissions@acm.org or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.


 

No entries found