Math Delights

by Dan Thomasson, from www.borderschess.org

Coloring a map seems like a simple task, but the task is more difficult when you have to determine the least number of colors needed to ensure that regions that share a border are drawn in different colors. In fact, the number of colors needed to color any map was proven with the aid of computers in 1976 — more than 100 years after the problem was posed.

Find a nice story about a map colorer online at www.c3.lanl.gov/mega-math/workbk/map/mpprstory.html, as well as some maps that need coloring.

Discover the smallest number of colors needed to color the map of the United States in such a way that two states sharing a common boundary are always colored with different colors. (Click on the map for a copy in a separate window that's easy to print.)

Learn more about why map coloring is a major area of research in computer science from CS Unplugged (http://csunplugged.org/index.php/en/13-graph-colouring-activitiesmenu-119, free account and login required), a wonderful website that teaches about computers without a computer.

Design your own maps. Figure out the least number of colors needed to color the maps, such that neighboring countries or regions have different colors.