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.
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).
Given any map, there is, however, a reasonably fast way to tell whether or not you can color it with two colors, and we do know you won't ever need more than four colors. The hard problem has to do with maps that can't be colored with just two colors. Will you need four colors to color it, or can you color it with just three? For some maps, we presently don't know any better way to tell if three colors will be enough than to try every possible combination of three colors to see if one of them will work.
To get an idea of how impractical this would be, select a map such as Bumpington, (which is relatively simple, in the sense that it doesnt have very many regions) and try to find a systematic way of counting all the different ways it can be colored with fewer colors--three colors or even two. Finding a way you could color it with just three colors. If you don't lose track completely, the number will be very large. For a very large map (one with many regions), it would take the fastest computers imaginable longer than the projected age of the universe to check out all the possibilities! The question of whether there is a fast method to find out if three colors is enough (and if so, what it is) is known as the P ?=? NP question. This is widely regarded as the most important unsolved problem in computer science, mathematical logic, and the foundations of mathematics.
One of the strategies they may 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. There is more information about greedy algorithms in Algorithms and Ice Cream for All
Surprisingly, Map #3 can be colored with two colors.
Some children may discover
a method for finding a 2-coloring (if the map can be 2-colored) by
following a "chain of logical deductions" as illustrated in Map #4:
In the leftmost map, one region has been colored red . If only red and blue will be used to color the map,
all of the regions which border the red must
be colored blue . (They can't be colored red, and blue is the only other color we want to use.) This is shown in the center map. In turn, the
regions bordering the blue must all be colored red . This is shown in
the
rightmost map. As we continue, we will either succeed in 2-coloring the entire
map, or get stuck. If we get stuck, , we know that a 2-coloring is
impossible, since we only did what we were logically forced to do up to
that point.
Notice the "checkerboard" character of a 2-coloring. Such checkerboard 2-colorings play a role in the mathematical study of knots and the study of surfaces in space.
After a while, some children may prefer to work with unifix cubes (or other colored marking pieces) to represent the colors assigned to the regions. This clearly (and concretely) represents a higher level of abstraction than the more-or-less permanent assignment of a color to a region using crayons. In fact, this is the manipulative employment of the concept of a variable, one of the most fundamental ideas in mathematics. The region is the variable that is assigned the value , a color. (Although students will probably not be very interested in the concept of variable and its usefulness, you will observe that working with "changeable markers" is a powerful problem-solving strategy for this problem.)
There is a simple (and surprising?) way to make "complicated" maps that can be 2-colored. The recipe is this: place pen to paper and draw a curve without lifting up your pen until you have returned to the starting point. The curve that you draw can intersect and cross itself any number of times.
Map #5a below is such a curve.
In Map #5b, a second curve has been drawn over the first one. Surprisingly, this map is two-colorable as well. In fact, you can draw any number of curves on top of one another and the resulting map will always be two colorable.
In the activity Make a Two-Colorable Map string and colored marking pieces are used to explore why this is true. The activity is a manipulative introduction to the idea of proof by induction a fundamental idea to which students are traditionally introduced in high school.
The basic principle of proof by induction is to begin by looking at the simplest possible case and demonstrate that what you are seeking to prove is true in the simplest case. Then you try to find a way to show how to add elements to that simplest case in a step-by-step, orderly fashion that is systematic enough to eventually cover all possible combinations of elements in all the cases. If you can show why, at each step, the truth that you demonstrated about the simplest case is preserved, you have completed a proof by induction.
It is important that students work with a variety of maps when they experiment with map coloring. The maps that are included with the activities in this chapter are meant as a starting point only. Additional maps are easy to draw, and you will learn a lot about map coloring by experimenting with maps to give to your students that will challenge them and let them apply what they know. And, of course, students will learn a lot when they make their own maps.
