Color a map of the United States with colors R, G, B, Y using as few Ys as possible.
Note: No adjacent states can have the same color. [Even through Utah and New Mexico meet at a point, as do Colorado and Arizona, these states are not considered adjacent for purposes of this problem. -Jeff]
An adjacency list for bordering states is given at the end of this page, as are Mathematica commands to produce a map of the U.S, shown above. (Thanks to Tom Whitesides (Kodak) for providing the data points for the map.)
Source: Problem by Joan Hutchinson (Macalester) and Stan Wagon (Macalester) using a Mathematica package with a four-coloring function written for the forthcoming "Mathematica Explorer" (WRI).
Adjacency list
AL --> {FL, GA, MS, TN}
AR --> {LA, MO, MS, OK, TN, TX}
AZ --> {CA, NM, NV, UT}
CA --> {AZ, NV, OR}
CO --> {KS, NE, NM, OK, UT, WY}
CT --> {MA, NY, RI}
DE --> {MD, NJ, PA}
FL --> {AL, GA}
GA --> {AL, FL, NC, SC, TN}
IA --> {IL, MN, MO, NE, SD, WI}
ID --> {MT, NV, OR, UT, WA, WY}
IL --> {IA, IN, KY, MO, WI}
IN --> {IL, KY, MI, OH}
KS --> {CO, MO, NE, OK}
KY --> {IL, IN, MO, OH, TN, VA, WV}
LA --> {AR, MS, TX}
MA --> {CT, NH, NY, RI, VT}
MD --> {DE, PA, VA, WV}
ME --> {NH}
MI --> {IN, OH, WI}
MN --> {IA, ND, SD, WI}
MO --> {AR, IA, IL, KS, KY, NE, OK, TN}
MS --> {AL, AR, LA, TN}
MT --> {ID, ND, SD, WY}
NC --> {GA, SC, TN, VA}
ND --> {MN, MT, SD}
NE --> {CO, IA, KS, MO, SD, WY}
NH --> {MA, ME, VT}
NJ --> {DE, NY, PA}
NM --> {AZ, CO, OK, TX}
NV --> {AZ, CA, ID, OR, UT}
NY --> {CT, MA, NJ, PA, VT}
OH --> {IN, KY, MI, PA, WV}
OK --> {AR, CO, KS, MO, NM, TX}
OR --> {CA, ID, NV, WA}
PA --> {DE, MD, NJ, NY, OH, WV}
RI --> {CT, MA}
SC --> {GA, NC}
SD --> {IA, MN, MT, ND, NE, WY}
TN --> {AL, AR, GA, KY, MO, MS, NC, VA}
TX --> {AR, LA, NM, OK}
UT --> {AZ, CO, ID, NV, WY}
VA --> {KY, MD, NC, TN, WV}
VT --> {MA, NH, NY}
WA --> {ID, OR}
WI --> {IA, IL, MI, MN}
WV --> {KY, MD, OH, PA, VA}
WY --> {CO, ID, MT, NE, SD, UT}
Mathematica code to generate a map of the continental US
Thanks to Tom Whitesides (Kodak) for providing the data points for the map and Stan Wagon (Macalester) for the Mathematica code. A copy of the Mathematica code is available as a separate file.
pts = {{-67.015406,44.863288}, {-68.048834,47.263288}, {-69.598977,47.163288},
{-71.149119,45.7}, {-70.726353,43.196622}, {-72.511365,42.863288},
{-73.356897,42.796621}, {-73.450845,45.129955}, {-75.047962,44.996621},
{-76.832974,43.696622}, {-78.711934,43.729955}, {-79.792336,42.463288},
{-79.62208,41.963288}, {-75.38107,41.963288}, {-74.845363,41.463288},
{-73.506097,42.063288}, {-72.032904,42.029955}, {-71.273986,42.129955},
{-71.050775,41.463288}, {-71.854335,41.296622}, {-73.996551,40.629955},
{-74.877181,39.129955}, {-75.581685,39.863288}, {-75.713779,38.496622},
{-75.009275,38.496622}, {-75.323187,38.029955}, {-77.296369,38.396622},
{-77.741926,39.346622}, {-78.166266,39.646622}, {-79.48172,39.279955},
{-79.524154,39.763288}, {-80.585004,39.763288}, {-80.54257,40.646622},
{-80.54257,41.979955}, {-83.310512,41.746622}, {-82.425422,43.046622},
{-82.779458,43.879955}, {-84.664009,45.846622}, {-88.590163,48.179955},
{-92.066938,46.779955}, {-87.596799,45.129955}, {-87.880617,42.496622},
{-87.360283,41.629955}, {-84.805918,41.729955}, {-84.773633,39.046622},
{-82.425759,38.446622}, {-82.027063,37.513288}, {-79.812087,38.396622},
{-75.778082,36.529955}, {-81.616774,36.596622}, {-83.612545,36.679955},
{-89.395819,36.529955}, {-89.167219,37.046622}, {-87.941094,37.913289},
{-90.573969,42.546622}, {-91.317488,43.513289}, {-96.505458,43.529955},
{-96.645254,46.029955}, {-97.161327,48.896622}, {-104.084813,48.996622},
{-116.027331,48.996622}, {-116.992599,48.996622}, {-124.280677,48.896622},
{-124.417844,42.029957}, {-124.001343,46.213289}, {-116.916417,45.979956},
{-117.045501,42.029956}, {-111.073895,41.996622}, {-111.003332,45.013289},
{-104.005423,44.963289}, {-104.005001,45.963289}, {-104.005001,42.996622},
{-96.569985,42.596622}, {-95.778252,40.663289}, {-95.422982,40.013289},
{-91.499361,40.379956}, {-94.638312,37.029956}, {-94.659519,36.496623},
{-90.481683,35.946622}, {-90.227196,36.429956}, {-89.718221,35.946622},
{-90.269611,34.979956}, {-88.127674,34.913289}, {-85.5828,34.996623},
{-84.246741,34.996623}, {-83.163429,34.979956}, {-81.089042,35.113289},
{-78.526565,33.796623}, {-80.946682,32.046623}, {-81.486297,30.713289},
{-80.143184,26.746623}, {-80.535638,25.196623}, {-82.440578,27.446623},
{-82.785134,29.029957}, {-83.737135,29.896623}, {-85.295666,29.846623},
{-87.508395,30.26329}, {-87.566119,30.979956}, {-85.007049,31.046623},
{-88.407889,30.36329}, {-89.553975,30.21329}, {-89.795256,31.029956},
{-91.624973,31.06329}, {-91.182624,32.896623}, {-94.206693,33.06329},
{-94.465347,33.629956}, {-100.033265,34.56329}, {-100.013237,36.546623},
{-103.056213,36.479957}, {-103.03544,36.996623}, {-101.996801,36.996623},
{-102.017574,39.996623}, {-102.014433,40.996623}, {-104.087309,41.01329},
{-109.04118,41.029957}, {-111.072763,41.046623}, {-109.04118,37.029957},
{-114.009724,37.029957}, {-120.136626,42.029957}, {-122.277235,36.56329},
{-120.033161,38.979957}, {-114.608669,35.01329}, {-117.282481,32.56329},
{-114.636089,32.646623}, {-111.092171,31.296623}, {-109.021568,31.36329},
{-108.145543,31.31329}, {-108.165749,31.76329}, {-106.439793,31.779957},
{-103.04672,31.996624}, {-103.242851,29.01329}, {-101.470817,29.76329},
{-97.157352,25.979957}, {-96.87106,28.36329}, {-93.855452,29.76329},
{-89.80164,29.096624}, {-114,42.03}, {-70.879,43.519}, {-71.8,45.12},
{-76,39.7}, {-90.1035,46.0469}, {-85.0495,46.6974}, {-85.4499,46.0469},
{-84.9,45.2}, {-86.5,41.62}, {-73.8499,40.8147}, {-113.094,45.0567},
{-115.807,47.438}, {-70.1921,43.9277}, {-70.0612,41.5888}, {-70.879,42.2594}};
states ={{100,97,98,99,84,83}, {78,106,105,104,82,81,79,80}, {124,125,126,117,118,122},
{120,123,124,122,121,119,64}, {117,110,111,112,113,114,115}, {17,16,146,20},
{24,25,22,23,140}, {99,98,97,96,95,94,93,92,91,90}, {90,89,86,85,84,99},
{76,55,56,57,73,74}, {69,147,148,61,62,66,67,137,68}, {43,42,55,76,53,54},
{43,54,45,44,145}, {77,75,112,111}, {47,46,45,54,53,52,51},
{135,136,101,102,103,104,105}, {5,6,7,16,17,18,19,150,151},
{140,29,31,30,28,27,49,26,25,24}, {1,2,3,4,138,149},
{145,44,35,36,37,38,142,141,41,143,144}, {40,39,59,58,57,56},
{76,74,75,77,78,80,79,81,52,53}, {101,100,83,82,104,103,102},
{60,61,148,147,69,70,71}, {88,49,50,85,86,87}, {59,60,71,58},
{73,72,114,113,112,75,74}, {5,138,4,139,6}, {15,23,22,21},
{126,127,128,129,130,109,110,117}, {121,122,118,137,67,119},
{8,9,10,11,12,13,14,15,21,146,16,7}, {35,44,45,46,33,34},
{111,110,109,108,107,106,78,77}, {119,67,66,65,64},
{14,13,12,34,33,32,31,29,140,23,15}, {20,19,18,17}, {89,88,87,86},
{58,71,70,72,73,57}, {50,51,52,81,82,83,84,85},
{131,132,133,134,135,105,106,107,108,109,130,129}, {117,115,116,68,137,118},
{50,49,27,28,48,47,51}, {8,7,6,139}, {65,66,62,63}, {55, 42,41,141,40,56},
{46,47,48,28,30,31,32,33}, {70,69,68,116,115,114,72}};
faces = pts[[#]]& /@states;
Show[Graphics[Line[Append[#, First[#]]]& /@ faces]];
© Copyright 1997 Stan Wagon. Reproduced with permission.