Points in the plane are each colored with one of two colors: red orcolor.

blue. Prove that there is a rectangle whose vertices are of the same

Printable View

- Nov 26th 2007, 07:24 AManncarplanesPoints in the plane are each colored with one of two colors: red orcolor.

blue. Prove that there is a rectangle whose vertices are of the same

- Nov 26th 2007, 11:33 AMOpalg
I found this clever argument here (amazing what Google will do for you). Take a 5×5 rectangular array of 25 points in the plane. Then each row must have at least three dots of one color. This means that there must be one color which appears at least three times in at least three rows. Each pair of such rows must have dots of this color in exactly one common column (since there are only five columns, and if they have two common columns it forms a rectangle). So the first two such rows collectively contain a dot in every row, and the third row has nowhere to put its three dots of that color without forming a rectangle, since it can only overlap each other row by one dot.

- Nov 27th 2007, 08:30 AMThePerfectHacker
Can you prove it for squares rather than rectangles?

---

The pigeonholing you did above reminds of the following nice problem: "Prove that if $\displaystyle 41$ rooks are placed on a $\displaystyle 10\times 10$ chessboard there will exist $\displaystyle 5$ peaceful rooks*".

*)By 'peaceful' I mean no 5 attack eachother. - Nov 27th 2007, 11:12 AMOpalg
I wondered about that, but I don't know the answer. There is certainly a lot of room for manoeuvre with the rectangles. You can specify that the sides of the rectangle are parallel to the coordinate axes (or any other two perpendicular directions), and you can require that the lengths of adjacent sides are integer multiples of any two specified real numbers.

If you replace the 5×5 array of points by a bigger one, say 100×100, you might perhaps hope that there would have to be a square of same-coloured points?