Date: Sat, 03 Jan 1998 16:50:17 -0500
From: William A. McWorter Jr.
Alexander,
Does the answer to pigeonhole #6 deserve a remark about the obvious generalization
| Partition the plane into n sets. Show that one of these sets contains the vertices of a rectangle. |
Grab any n+1 horizontal lines and any nn+1+1 verticle lines. The given horizontal lines meet a given vertical line in n+1 points; whence some pair of those points belong to the same set of the partition. Since there are at most nn+1 distinct ways a vertical line can meet the given horizontal lines relative to which sets of the partition are involved, some pair of the given vertical lines meet the given horizontal lines in the same pattern. Hence some pair of the given horizontal lines meet this pair of vertical lines all in the same set of the partition. This provides a rectangle whose vertices all belong to the same set of the partition.
Since this proof is exactly the same as the proof for the special case n=2, the remark doesn't need a proof.
(Or, color the cells of an n+1 by n^(n+1)+1 array in n colors in an arbitrary way. Show that some rectangle in the array has all its vertices the same color.)
William
| 41169935 |
