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