September 2006: It's a colorful country (solution)

There are several different answers to this month's puzzle. There are three problem states that make it impossible to color the country using only three colors: Nevada, Kentucky, and West Virginia. These three states have an odd number of neighbors. For instance, suppose we try to color Nevada and its five neighbors using only three colors. First, color Nevada blue. Then alternate colors around it: California red, Oregon yellow, Idaho red, Utah yellow. The problem is, Arizona borders Utah, California, and Nevada, so it can't be red, yellow, or blue. We need a fourth color. The same is true of the neighborhood around Kentucky and the neighborhood around West Virginia (notice that Kentucky and West Virginia are neighbors of each other).

So for the answer to the puzzle, one state has to be Nevada, California, Oregon, Idaho, Utah, or Arizona, and the other state has to be Kentucky, West Virginia, Ohio, or Virginia (the only states that border both Kentucky and West Virginia).

[We have not checked that all 24 pairs are attainable, but we have received at least 15 different solutions.]


This month's solvers: Evan Templeton, Kristin Jekielek, James Doyle, Helen Delano, Hiro Arai, Lisa Dubbs, Dulguun Bayasgalan, Jim Matthews, Judi Matthews, Susan Matthews, and Judi Matthew's high school math classes

September 2006: It's a colorful country

In 1852 Francis Guthrie noticed that it was possible to color all of the counties in England using only four colors (with bordering counties having different colors), and he conjectured that every map could be colored using four or fewer colors. For over a century the so-called four color problem was one of the most popular and elusive unsolved problems in mathematics. It did not become a theorem until 1976 when Kenneth Appel and Wolfgang Haken proved it using a computer to check thousands of special cases. Even now there is no pencil-and-paper proof of the theorem.

By the four color theorem we know that it is possible to color the continental United States using four colors. In fact, it can be colored using four colors so that one color is used for only two states. What are those two states?

Here is a blank map of the U.S.

Dickinson College students can submit answers to Dave Richeson or Barry Tesman. You do not have to submit your coloring, only the names of the two states (there is more than one answer). The list of solvers will be posted at the end of the month.