Have students color maps using the fewest number of colors while ensuring that bordering countries are different colors to expose them to optimization problems.

  • Motivate this activity with a story of a cartographer who cannot afford many colors, and thus needs to find the optimal way to color his maps.
  • This activity is an example of an optimization problem with multiple constraints (in this case, bordering countries cannot be the same color).
    • This gives students exposure to the types of real-world optimization problems they will encounter in the future.
  • When students have finished, have them explain how they know that they have found the minimum number of colors required to color the map.
    • Once they have done this, ask them to try to devise a map that requires five different colors. It has been proven that any map can be colored with only four colors, so this task will keep them occupied for some time!
  • For more information, visit the CS Unplugged Poor Cartographer Activity.