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.

The problem extends to finding rectangular grids of growing size. For example, from the intersection of 5 horizontal and 41 vertical lines with points colored in two colors one can extract 3 vertical and 3 horizontal lines all 9 of whose intersections are the same color.

To solve this, note that among any 5 points at least three must have the same color. Let's call it "dominant" for the given five points.

Thus, in every intersection of 5 horizontal lines by a vertical line we are able to select a dominant color. Having 41 lines and only two colors to choose from, we must be able to find 21 (out of 41) vertical lines whose intersections with the given 5 horizontal lines have the same dominant color. Call this color preferred.

Among 5×21 intersections, consider only those of the preferred color. There are at least 3 such on each of the 21 vertical lines. There are only 10 = C(5, 3) ways to select 3 items out of 5. In a collection of 21 possible selections from a set of 10 elements, at least one selection is bound to be included at least 3 times. The selections are located on at least 3 vertical lines and lie on at least 3 vertical lines.

A more general problem asks of the dimensions X×Y of an array colored with c colors to ensure the existence of an a×a monochromatic sub-array. The answer is given by two formulas:

References

1. R. Honsberger, From Erdös To Kiev, MAA, 1996, pp. 230-234.