Sunday, November 02, 2008

Manic Monday- colorful



Mo's word for Manic Monday is COLORFUL.



One of the most famous proofs in mathematics is the proof of the Four Color Theorem.

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.

The basic rule for coloring a map is that no two regions that share a boundary can be the same color. (The map would look ambiguous from a distance.) It is okay for two regions that only meet at a single point to be colored the same color, however. If you look at a some maps or an atlas, you can verify that this is how all familiar maps are colored.

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).

How many colors does it take to color this map?

Hint:

Colored marking pieces such as small pieces of colored paper or poker chips are useful for planning how to color a map.

If you want to try this

  • Right-click on on the uncolored line drawing
  • click on Save Image As
  • make sure you are saving to your Desktop
  • click Save
  • Go to your Desktop
  • Open the map.
  • Print it
  • Color it
Another HINT:

One of the strategies you might 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.

The answer is in the first comment, ah, the 4th comment.

HAVE FUN!

theteach


14 comments:

magiceye said...

very interesting post. had never thought of it. will work on it.

Felisol said...

Dear teach Mary,
this is almost food for my brain, but..I'll send my brother a link to your site. I think he might come up with the right answer.
I'll let you know in case.
From Felisol

Gemma Wiseman said...

This is so clever! I have never heard of this before! Colourful information!

maryt/theteach said...

The ANSWER is this map is a 2-color map. You can color it in with just 2 colors...Try it!

Hootin Anni said...

Hello Mary!!!

Tomorrow [actually tonight just before I shut things down blogging] I too have one VERY strong and opinionated blog...There is a meme that someone started [I can't remember who but I found it on RJFlamingo's blog --the link] That blogland is turning BLUE...I am making a special political BLUE stance. Make sure you come over if you can find time! I'll link to YOUR blog and your friends 'live' blog also!!!

GObama!!!

If you believe in prayer...use your connections...pray for the BLUE team.

See ya tomorrow.

Linda said...

To be honest, I never gave much thought to map coloring and certainly never knew that there was a mathematical way to do so!

Thanks for the new knowledge!

anthonynorth said...

Another interesting post - and a good brain-teaser.

Anonymous said...

Very interesting! I had no idea. You're such a great teacher. :)

My Colorful Contribution.

Durward Discussion said...

Somehow I'm a little disturbed that there is a "greedy algorithm" running around wild. :-)

Unknown said...

Oh my gosh! You're asking me to think????? LOL. Very interesting post!

Anonymous said...

I never gave this any thought, probably because I can't read maps at all. I bet my son would get a kick out of this though!

eastcoastlife said...

I don't like Maths but this looks fun! I'm going to try it. :)

Vinny "Bond" Marini said...

Interesting take on the theme this week...

I will not forget RT tomorrow!

Travis Cody said...

I've never thought of that. But it does make sense.

Cool post!