Subject: Re: Pigeonhole principle
Date: Sun, 8 Jun 1997 07:53:58 -0400
From: Alexander Bogomolny

Dear Lim:

The main thing with the pigeonhole principle is to devise quantities to which to apply it.

Draw three horizontal lines. We'll find a rectangle with vertices on two of these. The other sides are vertical. At the intersection with the three horizontal lines, every vertical line has three candidate points to serve as vertices of the sought rectangle.

Three points may be colored with 2 colors in 8 different ways. So, if you choose 9 vertical lines, there are bound to be triplets of points colored in the same manner. Select any two triplets colored in the same way - this gives you vertical sides. In any triplet, at least two points are of the same color. Select two such - this gives you horizontal sides.

Please see if this is clear and do not hesitate to ask more questions. Send me your solutions. I'll append them to the page. I'd also be happy to get more related problems.

Sincerely,
Alex Bogomolny