|
How many colors do you need to shade a map?
The small island nation of Seedonia is organized into three
provinces: Sciville, Connexia and Collabdale. |
One year, Connexia’s two best soccer teams played
to a 1-1 tie in the Provincial Championship. Being unable
to decide which team to send to the National Tournament, the
people of Connexia voted to split the province into North
Connexia and South Connexia so they could send both teams,
one from each of the new provinces. |
Some years later, for reasons that are not clear, Collabdale
split into Upper Collabdale and Lower Collabdale. Map publishers
in Seedonia became concerned about the rising cost of printing
maps since they had already gone from three to four colors
when Connexia split. How could they avoid using the same color
for adjacent provinces without adding a fifth color?
One mapmaker solved the problem like this: |
Moreover, he claimed that he could also color the ocean,
which in earlier maps had been left blank, without adding
a color. He even claimed that no matter what course Seedonia’s
political future took, he could color any map, regardless
of how many provinces there were and no matter how they drew
their borders, using only four colors. No two adjacent provinces
would have to be in the same color.
Is he correct? Can you come up with a map -- real or imaginary
-- that requires more than four colors? The key requirement
is that no region can share an edge with another region of
the same color. Corner touching is OK. For example, this map
uses only two colors and doesn’t violate the rules: |
 |
Try it with a friend. One of you can draw a difficult map for the
other to try to color.
If you can’t find a map that requires more than four colors,
can you prove that no more than four are ever needed?
Make up some puzzles like these and send them in with your solutions.
We’ll post them here in the SEED Science Center.
|
|
Things To Do
Science
Center
Schools
SEED People
