How many different colors must you have available if you want to color a map so that countries that share a boundary line are not colored the same color? In the mid-1800's this problem became known among a small group of mathematicians as a popular unsolved problem. Even at that time, it was common knowledge among map-makers that 4 colors seemed to be sufficient to color a map. This wasn't actually proved, however, until 1976.
The basic rule for coloring a map is that no two regions that share a boundary can be the same color. (The map would look ambiguous from a distance.) It is okay for two regions that only meet at a single point to be colored the same color, however. If you look at a some maps or an atlas, you can verify that this is how all familiar maps are colored.
Even though we now know that 4 colors is enough to color any map, some maps can be colored with fewer colors--three colors or even two. Finding a method to determine exactly how many colors is needed for any map continues to daunt mathematicians today. Some mathematicians believe that a fast method to find out the minimum number of colors needed for a map is impossible (that is, it simply does not exist and hence can never be found).
How many colors does it take to color this map?
Colored marking pieces such as small pieces of colored paper or poker chips are useful for planning how to color a map.
If you want to try this
- Right-click on on the uncolored line drawing
- click on Save Image As
- make sure you are saving to your Desktop
- click Save
- Go to your Desktop
- Open the map.
- Print it
- Color it
One of the strategies you might discover is the Polka Dot Strategy of using one color to exhaustion before taking up another one. The polka dot strategy has a colorful mathematical name. It is known as a Greedy Algorithm. Greedy Algorithms are one of the four or five most basic and general algorithm design strategies used in computer science.
The answer is in the first comment, ah, the 4th comment.