Coloring Problem
Who doesn’t love coloring problems? They’re like one of the staples of recreational mathematics, right up there with combinatorial and polynomial problems. They occur in serious math too: the four color theorem, for example, and various other graph theoretical questions. Some of these have been found to have practical applications. Maybe this one, which has stumped the UHME mailing list for a while now (and is therefore not likely to be worked on much more) has a practical application:
Color the (x,y)-plane in two colors, i.e. color every point in the
plane either blue or red, say. Will there always exist two points at
distance one which are the same color? What about three colors? Four
colors? More?
Possibly relevant posts:
- Zach’s strange fractional part problem (12/22/2004)
- Connectedness of the set of feasible
-colorings (2/21/2007) - Oldies but goodies (7/3/2005)
2 colours…
Assume that no two points with distance one will be the same colour.
Colour (0,0) to begin… red, say (without loss of generality).
Therefore, the points around the unit circle must be blue.
However! We can pick 2 points on a chord of the circle which have distance 1.
say (0,1) and er.. (1/4, sqrt(3)/2), which we said must both be blue?
This contradicts our assumption!
So there must be two points which are the same colour in the two colour case!
Now three colours
Colour (0,0)… red, say.
Now the points around the unit circle are… uh… not-red.
We can pick (0,1) again, and colour that. It’s not red so let’s say… blue.
Now, we know that a circle around that is not-blue, hurrah!
Thus, (1/4, sqrt(3)/2) [[and (1/4, -sqrt(3)/2)]] must be neither red or blue, so it’s green.
Humm… now we can draw a circle around that green point, I suppose, and check the new intersections formed - these are limited, and continue, forming a pretty pattern, which I guess (from drawing a quick picture) doesn’t immediately contradict.
I’m interested in how this relates to the four-colour map theorem, and therefore I am expecting the three-colour version to not be possible in some way…
Comment by Ronald — 12/22/2004 @ 3:14 pm