All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Shapes
Map coloring (Posted on 2015-06-05) Difficulty: 2 of 5
Imagine an island composed of several connected countries with no enclaves or exclaves. We are concerned with coloring a map of the island with as few colors as possible.

If two neighboring countries merge their border dissolves and they become the same color.

Begin with an island that can be two colored.

One or more pairs of countries merge and now the new map of the island can only be three colored.

Again, one or more countries merge and now the map of the island requires four colors.

Find the smallest number of starting countries for which this is possible as well how they are joined.

A diagram like this example of a 3 color map should be easy enough to read:

1122
1332
1122

  Submitted by Jer    
Rating: 3.3333 (3 votes)
Solution: (Hide)
The minimum of 6 regions is as shown:
1145
1236
1166

Where 1,3,5 can be one color and 2,4,6 the other.
Erase the west border:

1145
1136
1166

With 2 gone, 1&5 can be the same color but 1,3,4 must be different but 6&4 can be the same.
Erase one more border:

1144
1136
1166

Now all four regions must be different colors.
The map seems to be the smallest possible, using a grid of only 12 squares.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
A further challenge.Jer2015-06-06 21:01:25
re: 6 countries solutionSteve Herman2015-06-06 06:23:51
Solution6 countries solutionBrian Smith2015-06-05 22:50:02
QuestionPuzzle challengedSteve Herman2015-06-05 20:23:52
re(3): Drawing Challenged (spoiler?)Steve Herman2015-06-05 14:00:13
re(2): Drawing Challenged (spoiler?)Jer2015-06-05 10:51:11
Some Thoughtsre: Drawing Challenged (spoiler?)Steve Herman2015-06-05 09:52:09
Some ThoughtsDrawing Challenged (spoiler?)Steve Herman2015-06-05 09:40:25
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information