Optimization in Four Colors

I suspect many (most?) geometry teachers know of the Four Color Theorem (FCT) which roughly states that any flat map, no matter how complex, containing only contiguous regions with finite perimeter can be colored with no more than four colors with the only restriction for coloring being that regions have different colors if they share any boundary beyond a set of finite points. While the FCT is not a particularly useful to cartographers, it has historical significance as the first significant mathematical proof to have been established with extensive use of computers.

THE PROBLEM:  In secondary geometry classes, the FCT is typically just a footnote or factoid, but it is pretty easy to understand for students of all levels.  This year I decided to make it more interesting as an optimization problem.  If each color you use has a different “cost” per area unit, can you color a given map as “cheaply” as possible?

[I considered a maximum cost map, too, and convinced myself that the maximum cost map is just a flip of all the colors, assuming the change in cost is the same between all colors.  With that thought, saving money seemed the more "realistic" goal, so I went with minimum cost.]

MOTIVATIONS:  Perhaps the BEST part of this project was that I was not–and still am not–convinced that we have found THE optimal solution.  I was reasonably certain that I could determine a very good mapping cost, but the sheer number of possibilities would require significant computer run time and coding abilities (just like the original FCT proof!) to ferret out the best answer–resources not available to those solving the problem (the computing problem is an issue my school is actively addressing).  I loved having a problem in math where determined students might best their teacher–and some did!!  I also liked that this project significantly motivated my students to use spreadsheets to track their data–a different math resource than most were accustomed to using.

IMPLEMENTATION:  Experimenting, I decided to offer different versions of the coloring challenge to my 4th-5th grade math club and all of my 8th grade math classes (prealgebra, algebra, & geometry).

Project 1:  Our 8th grade humanities course had an Africa unit earlier in the year, so I returned there by asking all of the students to color this map of Africa.

Africa

We provided this spreadsheet of country names and areas along with these coloring costs:  Purple = $2.00/mi^2, Yellow=$2.50/mi^2, Red = $3.00/mi^2, and Blue=$3.50/mi^2.  After some discussions on the first day, the “border” rule was revised to note that countries whose borders were only large lakes (Democratic Republic of the Congo & Tanzania plus Chad & Nigeria) could be considered “not touching” for this project.

Political incorrectness confession:  We noticed a day after we assigned the project that we had inadvertently left off the relatively new South Sudan. I decided to leave the two Sudans as a single country for this exercise (thus the inked in portion of the map).  Having compromised the previous day on the lake-bordered countries, my error accidentally made the largest and 3rd largest African countries border each other–a nice confounding problem, I thought, for forcing students to determine which would get a cheaper color.

Project 2:  I gave the relatively simpler map of the lower 48 US States to our 4th-5th grade math club with coloring restrictions Red=$1.00, Yellow=$1.25, Blue=$1.50, and Green=$1.75.

USA

RESULTS:  For the submission, students (in ones or pairs) had to submit their colored map, a spreadsheet showing their computations, and 1-3 paragraphs explaining their general coloring strategies, and especially how they handled the inevitable situations where their coloring strategies self-conflicted.  In general, we could have done a better job preparing students for the written portion, but the two most commonly stated strategies were

1. (Low level) We colored the biggest countries the cheapest as far as we could, and then colored the next largest using the next cheapest color, etc.  If we ran into conflicts, we “worked it out”.

2. (Stronger) Noticed after trying the obvious strategy above that the countries colored the 2nd cheapest surrounding a “cheapest color” country often had more area than the “cheapest color” country.  By paying a little more for the largest country, they more than made up for the added expense by coloring a collection of countries that in total had more area.

3. A  few members of my math club addressed some specific strategies like the 11-state ring of US states (MO-IL-IN-OH-WV-VA-NC-GA-AL-MS-AR) surrounding Kentucky & Tennessee made it possible to use just two alternating colors over a large area.

Using our color schemes, excellent scores for the US map were very close to, but just over $1,000,000.  The best Africa map scores we found were just under $17,000,000.  As I noted earlier, I’m not at all convinced that we have found the optimum values, but part of the fun of these projects was that anyone with some calm logic and determination could break through.  My second best coloring scheme was from a student who had been exposed to the least amount of math.  If you can beat these scores, please share.

VARIATIONS:  After playing with this for a while, I’m convinced that all optimal solutions depend on the gap you set between the color costs.  The more expensive the next color is, the more motivation you have to not change colors.  I haven’t tried it, but I think strategy #2 above could be exploited more often if paint color jumps are smaller on a large, complicated map.

I’m also convinced that the initial paint cost is irrelevant.  It will change the total cost of the project, but it would just scale all values up or down.

I didn’t play with different step values in paint cost, but I can see that potentially changing the game, especially if the cost jumps increase as you approach the 4th color.

Enjoy.

About these ads

One response to “Optimization in Four Colors

  1. I agree that making the steps unequal or geometric would be the next step to enhancing this problem. This reminds me of the scoring system of GreeGlobs–the more hits per shot payed off tremendously. It might be wise to reduce the states to 24 for expediency in exploration, but the buy with the US is hard to beat.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s