Hint for problem on $4 \times 7$-chessboard problem related to pigeonhole principle
Suppose that each square of a $4 \times 7$ chessboard is colored either black or white. Prove that with any such coloring, the board must contain a rectangle (formed by the horizontal and vertical lines of the board) whose four distinct unit corner squares are all of the same color?
Any hints on this problem, I guess it could be solved with a clever application of the pigeonhole principle, but I have some difficulty seeing what the objects and what the bags are in which to put the objects to apply the pigeonhole principle, and then argue that such an coloring must exist. It is taken from a textbook on discrete mathematics, and in the text a version of the Monotone Subsequence Theorem by Erdös/Szekeres is proven (using the pigeonhole principle). Hence, I guess it is somehow related to this.
Solution 1:
Let's say the chessboard has $4$ columns and $7$ rows. Each row must land in (at least) one of the following $6$ bags:
- First and second squares are black.
- First and third squares are black.
- Second and third squares are black.
- First and second squares are white.
- First and third squares are white.
- Second and third squares are white.
By the pigeonhole principle, two rows are in the same bag, and that gives you your rectangle with all four corner squares of the same color.
Note that you only need a $3\times7$ chessboard for this to work.
Solution 2:
Consider the case where we have a monochromatic row ($4$ black squares) the next rows must either have $1$ or $0$ black squares and in order to avoid both a white or black rectangle, we can only add one more row.
Now consider the case where the first row has $3$ black squares, one can rapidly show that there are three more rows that we could add before a fifth row would cause a monochromatic rectangle.
Best we can do is have the following $6$ rows each containing $2$ black & $2$ white squares, and a seventh row will cause a monochromatic rectangle.
