Monochromatic rectangle on a two-colored plane

[bonanova]

This problem is adapted from a problem given in the 1976 USA Mathematics Olympiad.

 

Prove or disprove:

 

Any 2-colored plane contains an m x n monochromatic rectangle (4 vertices of same color) such that

1. m = 1 or 2, and
2. n <= 6.

[Rainman]

Consider coloring the corners and intersections in this figure, either red or blue. Suppose it can be done so that no monochromatic rectangle exists.

Let (a,b) denote column a, row b, according to the numbers in the figure. If any column has all three points of the same color, change one of them to the other color. For example, if (3,0), (3,1), and (3,2) are all red, change one of them into blue. This change can never result in a new monochromatic rectangle appearing, so we still have no monochromatic rectangles. Repeat this process until all columns have both colors. There are six possible coloring patterns for a column: RRB, RBR, RBB, BBR, BRB, and BRR. However, there are seven columns, so two of them must have the same pattern. This will yield a monochromatic rectangle. For example, if columns 2 and 5 are both RRB, then taking the two red points from each column yields the rectangle (2,0),(2,1),(5,1),(5,0) which is all red and is of size 1x3. So there will always be a monochromatic rectangle in this figure. Finally note that any monochromatic rectangle from this figure is of requested size.