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:
- BBB or BBW,
- BWB,
- WBB,
- WWW or WWB,
- WBW,
- BWW.
I'm having trouble with this problem. Any help or hints would be appreciated.
Best Answer
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.