True or False: Every map whose countries are quadrilaterals that meet edge-to-edge can be 3-colored.For example, a checkerboard is (a very simple example of) the sort of map we are considering. It can be 2-colored.
NOTES:
I should add that edge-to-edge includes the possibility that one quadrilateral meets another in TWO edges, which can happen if they are nonconvex.
- Maps are assumed to be in the plane.
- The exterior region (the "ocean") need not be counted as a country.
- A coloring must use different colors on countries that share an edge.
- "Meet edge-to-edge" means that any pair of countries that meets does so either in a single point or a full edge of each country.
To underscore that "full edges" means the following is not allowed:
---------------- ----------- |Quad #1 Quad #3 | |------------- | Quad #2 ---------------- ----------------MOTIVATION:
The motivation will be explained next week. But I can here announce that Tom Sibley (St. Johns University) and I have just proved (by a VERY short proof!) that any (finite or infinite) Penrose rhomb tiling is 3-colorable. The Penrose kites and darts situation remains open, though it has been conjectured for almost 20 years that they too are 3-colorable. This week's puzzle arose in our work (and was solved by Rick Mabry (LSU/Shreveport)). Our coloring result is much more general than the Penrose case and details will be posted next week.Late news: Michael Schweitzer has taken our proof and made it even shorter!
© Copyright 1999 Stan Wagon. Reproduced with permission.