CS Unplugged activity
The Poor Cartographer
A cartographer draws maps for a living, but she is too poor to own many crayons. It doesn’t matter which color a country is, so long as it’s different to all the countries touching it. In this activity you’ll color her maps for her, using as few colors as possible.
The one rule
Two countries that share a border must be different colors. Countries that only touch at a single corner point are allowed to match. Here’s a tiny map, already colored:
If we color Northland red, then Westland and Eastland cannot be red, since their border with Northland would be hard to see. We could color Westland green, and it is also acceptable to color Eastland green, because it does not share a border with Westland. Southland can be colored red, and we end up needing only two colors for the whole map.
If you don’t have colored pencils, use four different patterns instead: dots, stripes, crosshatch, and plain. A pattern works exactly like a color here.
What to do
Color in the countries on each map below with as few colors (or patterns) as possible, but make sure that no two bordering countries are the same. Try coloring lightly at first, so you can change your mind.
Colors or patterns used on Map 1: Map 2 (top): Map 2 (bottom): Map 3: Map 4:
Two of these four maps can be colored with just two colors. Which ones? Once one country on a map like that is colored, what does that tell you about every country touching it?
Look at whichever map needed four colors. Can you find four countries where each one touches the other three? That’s how you can prove four colors are really needed, without trying every other combination first.
Learn more: this is called graph coloring, and it also shows up in scheduling problems, like building a class timetable with no student double-booked.
What’s it all about?
The problem you just solved is really about finding the smallest number of colors needed for a map. The idea that any map can be colored with only four colors was first guessed in 1852, but nobody managed to prove it until 1976. That’s over a hundred years of computer scientists and mathematicians chipping away at one question.
Map coloring belongs to a bigger family of problems called graph coloring. Draw a dot for each country and a line between any two countries that share a border, and the coloring rule becomes: no two dots joined by a line can share a color. The same idea can stand in for all sorts of things other than countries, like school subjects that can’t share an exam period because some student takes both.
Small maps like the ones on this page are easy to color by hand. But as a map (or a school timetable) gets bigger, checking every possible way to color it takes longer and longer, the same way it did for the Muddy City problem’s harder cousin, the traveling salesperson. Finding the fewest colors for a huge map is one of those problems computer scientists still don’t have a fast method for.
Solutions and hints
Map 1. This is the only possible solution (of course, the choice of colors is up to you, but only two different colors are required).
Map 2. The map at the top can be colored correctly using three colors, while the one at the bottom requires four. Here are two possible solutions.
Map 3. A simpler three-color map, with a possible solution shown here.
Map 4. A solution using just two colors (shaded and white).
Version history
- Loading commit history…