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

Home > Shapes
Paint Job Pro (Posted on 2006-09-19) Difficulty: 4 of 5
The famous four-color-theorem states that every map can be colored with no more than four colors, such that no two adjacent regions receive the same color. Two regions are called adjacent if they share a border segment, not just a point.

There are certain types of maps however, where less than four colors are sufficient:

1. We partition the plane into regions by drawing a number of straight lines. In the resulting "map" there will be some infinitely large regions, but that shouldn't bother us. How many different colors do you need for such types of maps?

2. Instead of straight lines, partition the plane by drawing circles. How many colors are needed now?

3. What if you draw circles and chords?

4. Now consider 3-dimensional "maps", where you partition space into regions and two regions are called adjacent when they share a common (2-dimensional) face, not just an edge or a point. How many colors do we need if space is partitioned by planes?

5. As above, but with spheres instead of planes.

6. How many colors are required for general 3-dimensional maps?

No Solution Yet Submitted by JLo    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Necessary Colors Comment 2 of 2 |

For #1 and #2, only two colors are needed assuming the lines are infinite.  Each line or circle partitions the plane.  Simply invert the existing colors on one side of the line or circle when a new line or circle is added.

No fixed number of colors is sufficient for #6, as any number of regions in 3D space can simultaneously border each other.

If drawing an infinite plane or sphere which partitions the space is required (#4 and 5) then as in #1 and 2, then two colors will again suffice.

For #3, four colors can be proven to be necessary in an arbitrary map.  Draw a large circle and inside it a smaller circle.  Then draw three non-intersecting segments from points on the smaller cirle to the larger circle.  All four regions have a border with the other, requiring four colors.

The above is NOT the Four Color Theorem (4CT).  The above paragraph proves four colors are necessary.  4CT proves that four colors are sufficient.

  Posted by Brian Smith on 2008-01-01 01:39:47
Please log in:
Remember me:
Sign up! | Forgot password

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

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information