Monday, August 4, 2008

A painted plane

1.
Let's say I've painted a plane--the flat kind, not the flying kind. Every single point on the plane is assigned the color red or blue. Prove that there must exist two points of the same color that are exactly one unit apart.

2.
Every single point on the plane is assigned the color red, blue or green. Prove that there must exist two points of the same color that are exactly one unit apart.

Update: Yoo Chung has explained the solution here.
My additional comments are here.

5 comments:

Yoo said...

The first problem is pretty easy with a proof by contradiction, but the second problem is driving me crazy!

Ólafur Jens Sigurðsson said...

Hmmm, I must be misunderstanding something here. The first part is disproven by contradiction easely by painting the plane in the two colors on each half of the plane and no two points with the same color have another color between them

ooooxxxx
ooooxxxx
ooooxxxx
ooooxxxx

If by "one unit apart" you mean that the points must be adjacent then you can create a chess board and no two adjacent pieces have the same color

oxoxoxox
xoxoxoxo
oxoxoxox
xoxoxoxo

What am I missing here? Is it the word "unit" that I am misunderstanding?

Yoo said...

You're not thinking of a continuous plane, and you're not thinking of a unit as simply a distance of 1.

The first one can be easily proven by picking any point colored blue and thinking of what the points a unit away has to be colored, but a straightforward extension of this proof doesn't work for the second.

miller said...

It is a continuous plane. One unit could mean an inch, a centimeter, it doesn't matter.

The second question is also a proof by contradiction.

Yoo said...

I'm finally free of this puzzle. Hopefully it hasn't already driven me insane ...