One of my favorite theorems to learn about in math was the Four Color Theorem. The theorem states that any contiguous separation of a plane (called a map) can be completely colored by at most four colors such that no area touches another area of the same color. When my son, Max, asked for a US map to color, I saw my opportunity to introduce him to this theorem!
After printing a map of the Contiguous United States (no AK, HI), I challenged him to color the map so that no two adjacent states were the same color. After a small mishap in the midwest, he easily completed a map coloring. After changing the colors of a few states, we even produced a “balanced” coloring of the map, so that there were 12 states covered by each of the four colors he used. We even had fun tracing “paths” from coast to coast, from most any state to another while avoiding a selected color. For example, we were able to make it from California (blue) to Georgia (green) without touching any states that were colored yellow.
This week’s GeekDad Puzzle of the Week is the same challenge: Use the map (below) or a similar map to produce a balanced four color map of the contiguous US. Each correct entry will have a shot at winning this week’s fabulous prize, a ThinkGeek Gift Certificate.
Click to embiggen for printing.
For an additional challenge (and an additional entry in the prize drawing) explain why it may or may not be possible to trace a path from any given state to any other while avoiding a given color (assuming neither the start nor the end state is that avoided color.) For purposes of this part of the puzzle, consider the “Four Corners” (UT,CO,NM,AZ) to all be touching one another.
A sample map, as sent in by our randomly selected winner, Andrew Gehman, shows a nice balanced, four color coloring of the map. Congratulations! His map appears below, and a $50 Gift Certificate from ThinkGeek will be on the way to him shortly!
The second part of the puzzle was a little more challenging. Because of the high degree of adjacency of the US States, it would be challenging not to find a work around to go from any state to another while avoiding a target color. Looking at an adjacency matrix of the Lower 48, we can see a few interesting “bottlenecks”:
There are four US States (FL, RI, SC, and WA) that are adjacent to only two other states. For example, FL borders only GA and AL, so care would have to be taken in construction paths to or from FL. However, because this is a four colored map, the path would still (theoretically) be possible. If you are having challenges with your map, sometimes the trick lies in the color(s) of TN and MO, the two most highly connected states.
There is one US State that could make for an “impossible” path: ME. The state of Maine is bordered only by NH (New Hampshire), so if NH was the “avoid” color, paths to or from ME could not be so constructed.
Many thanks to everyone that posted a response. I hope that this puzzle was a fun to solve as it was to write. Happy puzzling!
Liked it? Take a second to support GeekDad and GeekMom on Patreon!
