Methods of Proof 343Next, look at the lineA 2. Either there is a rectangle of colorc 1 , or at most one point
M 2 jis colored byc 1. Again by the pigeonhole principle, there is a colorc 2 that occurs
infinitely many times among theM 2 j’s. We repeat the reasoning. Either at some step we
encounter a rectangle, or after finitely many steps we exhaust the colors, with infinitely
many linesAistill left to be colored. The impossibility to continue rules out this situation,
proving the existence of a rectangle with vertices of the same color.
Here is another solution. Consider a(p+ 1 )×(n
(p+ 1
2)
- 1 )rectangular grid. By the
pigeonhole principle, each of then
(p+ 1
2)
+1 horizontal segments contains two points of the
same color. Since there are at mostn
(p+ 1
2)
possible configurations of such monochromatic
pairs, two must repeat. The two pairs are the vertices of a monochromatic rectangle.
51.We place the unit square in standard position. The “boxes’’ are the vertical lines
crossing the square, while the “objects’’ are the horizontal diameters of the circles (Fig-
ure 50). Both the boxes and the objects come in an infinite number, but what we use for
counting is length on the horizontal. The sum of the diameters is
10
π= 3 × 1 +, > 0.
Consequently, there is a segment on the lower side of the square covered by at least four
diameters. Any vertical line passing through this segment intersects the four correspond-
ing circles.
Figure 5052.If three points are collinear then we are done. Thus we can assume that no three points
are collinear. The convex hull of all points is a polygon with at mostnsides, which has
therefore an angle not exceeding(n−n^2 )π. All other points lie inside this angle. Ordered
counterclockwise around the vertex of the angle they determinen−2 angles that sum up
to at most(n−n^2 )π. It follows that one of these angles is less than or equal to(nn(n−−^2 )π 2 )=πn.
The three points that form this angle have the required property.
53.Denote byD(O, r)the disk of centerOand radiusr. Order the disks