Monday, October 13, 2008

A painted plane III

The painted plane returns! See previous parts: part I and part II.

1.
I've painted a flat, infinite, continuous plane. Each point on the plane is either painted red or blue. Prove that there must exist four points of the same color which form the corners of a rectangle.

2.
I've painted the plane again, this time using a large (but not infinite) number of colors. Prove that there must exist four points of the same color which form the corners of a rectangle.

Update: The solution has been posted already.

2 comments:

The Barefoot Bum said...

Since you're posing the problem, I'm going to assume (since I lack the time or mathematical ability to actually solve the problem) that the solution is not just a trivial extension of the triangle problem.

Which then raises the question: is there a general solution for the m/n (finite) problem, where you have a plane painted with m colors, and you have to prove you can draw a regular n-gon with all corners (vertices?) of the same color.

How about any definable shape/curve with a finite number of control points?

How about fractal shapes and curves with infinite control points that are non-space-filling?

(I suspect it's trivial to show that a space-filling fractal cannot have all of its control points of one color.)

miller said...

This problem (and the other painted plane problems) are questions that relate to the branch of mathematics called Ramsey Theory. Ramsey Theory has a reputation for having complicated proofs involving insanely large numbers (eg Graham's number). I do not know whether current Ramsey Theory can answer your questions.

The rectangle problem, though, requires much smaller numbers. (Hint!) 21 points will suffice to show that a single-colored rectangle must exist on a 2-colored plane.