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.
Monday, August 4, 2008
Subscribe to:
Post Comments (Atom)
5 comments:
The first problem is pretty easy with a proof by contradiction, but the second problem is driving me crazy!
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?
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.
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.
I'm finally free of this puzzle. Hopefully it hasn't already driven me insane ...
Post a Comment