### Brain Teasers

# Color the Map

What is the fewest number of colors you can use to color the states of the USA if no states of the same color can touch?

### Answer

4 colors.In fact 4 colors will suffice for any map, real or fabricated. Although, it took over 100 years for mathematicians to prove this fact.

Hide Answer Show Answer

## What Next?

View a Similar Brain Teaser...

If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.

### Solve a Puzzle

## Comments

You will never know how long I spent with a world map, pack of Cub Scouts, and set of felt pens to check this one out!!

That's a pretty neat teaser, I got it wrong yet it was still very interesting!

a good bit of math trivia

Yes, almost fits the trivia category. It may have taken a hundred years to prove it but the 4 colour map problem is a well established piece of modern Mathematical theory.

With all the math it took to prove this problem did any of you think that if you colored all the states the same color no two colors would touch. Doesn't 1 seem like the simple and obvious answer.

I think the wording of the teaser should be "if no two states of the same colour can touch".

i just happened to know this one, It would be cool to see mathematical/geometrical proof though

The answer may seem rather obvious, but it is unbelievably difficult to find a rigorous proof that applies to any imaginable map, and it took computers to get the final valid proof. There are various sites on the Internet that give the story of the Four Color Theorem, for example http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html

Jake.. Thanx for the information ! I will say that in class ... Neet teaser ... As they say in french :

Chapeau

Chapeau

This only holds true for 2 dimensional maps. Not that I know the minima for 3 or more dimensions.

But, what if one country borders to four countries?

It took me a while... and I still got it wrong, but great one anyways

From my understading, there is no actuall proof, a computer than ran every concievable map layout and proceeded to color it in in the most effiect way possible and could not come up with a counter example.

The 4-color problem was reduced to a problem involving checking a finite number of cases. These cases were then checked by computer. So, if you trust the results of the computer program, it has been proven. A lot of mathematicians, however, do not believe that a computer should be used in this way in a proof.

From Canu's link it sounds like it has been proven, since it was shown to be true for every possible case within the unavoidable set. What an interesting problem.

To post a comment, please create an account and sign in.

## Follow Braingle!