Problem: The squares in the $3$ (columns) by $7$ (rows) grid are colored black and white. Can we guarantee that the board contains a rectangle (of size $n \times 2$ or $n\times 3$, with $n >1$) whose four corner squares are all black or all white?
Attempt:
rows: $7 \to 6$ color schemes:
I'm having trouble with this problem. Any help or hints would be appreciated.
Two squares that lie in the same column and have the same color will be called a doublet. Since each column contains at least one doublet, the $3 \times 7$ board contains at least seven doublets. By the Pigeonhole Principle, at least four doublets are the same color, say, black. Now, each doublet determines a pair of rows. Since there are more than three black doublets but only $\binom{3}{2} = 3$ pairs of rows, two black doublets determine the same pair of rows (again by the Pigeonhole Principle). The four black squares that comprise these two doublets are the corners of the desired rectangle.
More generally:
Suppose that every square of an $m \times n$ chessboard is painted with one of two colors (say black or white). A rectangle of the chessboard that has all the four corners of the same color is called a chromatic rectangle. We will call an $m \times n$ chessboard a CR-board if every black and white coloring contains a chromatic rectangle. A $m \times n$ chessboard colored with two colors is a CR-board if and only if it contains a $3 \times 7$ or a $5 \times 5$ board.
There is also a sufficient condition for the existence of a chromatic rectangle:
Suppose that $N$ squares in a $m \times n$ board are colored black. Let $N = nq + r$, where $0 \le r < n$. If \begin{align*} r\binom{q+1}{2} + (n-r)\binom{q}{2} > \binom{m}{2} \end{align*} then there is a rectangle all of whose corners are black.
I wrote something about this with colors red an blue. Should be easy to adapt: By the pigeon hole principle, at least $4$ of the dots in the first column must be of the same color, say red. Then consider the $8$ dots which share the same rows with our $4$ dots in the first column but are in either column $2$ or $3$.
At least one of those $8$ dots must be red since otherwise, we can easily find a blue monochromatic rectangle. Suppose that this red dot is in column $i$ for $i = 2$ or $i = 3$. If any of the other three dots in column $i$ which were part of our $8$ dots above are red, then we can find a red chromatic rectangle with column $1$. Therefore, they must all be blue. Now consider the $3$ dots immediately to the left or to the right of these $3$ blue dots depending on the $i$. By the pigeon hole principle, $2$ of these must be of the same color. However, if any $2$ are red, we can form a red monochromatic rectangle with column $1$ and if any are blue, we can form a blue monochromatic rectangle with column $i$. Therefore, we can always find a monochromatic rectangle in a $7 \times 3$ grid.
