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.