perplexus.info :: Shapes : Paint Job Pro

Paint Job Pro (Posted on 2006-09-19)

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?

Submitted by JLo

No Rating

Solution: (Hide)

Two colors is the right answer for #1, #2, #4 and #5. Proofs are identical, let's look at #1. as an example:
For only one line this is clear. Say we have a scenario with n lines and a red-green coloring. How can we obtain a coloring when an extra line is added? Just leave one side of the new line as is and revert red and green on the other one. So the statement follows by induction. Another way to see it, is to "calculate" the color of each point of the plane by adding a 0 to the point when it is on the left, 1 when it is on the right side of a line (Just deem any side of a line as left, it does not matter which, initially points are given the value 0). Do the calculation modulo 2 and then color the 0-points red, the 1-points green.
For circles and chords, three colors is the answer. To see this, use the "add-modulo" trick, but now add 0, 1 and 2 to any point in the plane according to their position of the individual circles and their chord.
For general 3-dimensional maps, an arbitrary number of colors may be needed, just think of long "worms" as cell, where each one is touching each other.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
Necessary Colors	Brian Smith	2008-01-01 01:39:47
No Subject	Jer	2006-09-19 12:38:19

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 (13)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info