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

Share Have students color maps using the fewest number of colors while ensuring that bordering countries are different colors to expose them to optimization problems. with FacebookShare Have students color maps using the fewest number of colors while ensuring that bordering countries are different colors to expose them to optimization problems. with Twitter
  • 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.

Tags

External Source

CS Unplugged Poor Cartographer Graph Coloring Activity

Other Tips By
Other Tips By CS Unplugged