Given an 8×8 array of dots colored either red or blue, prove their must exist a monochromatic rectangle regardless of how the 64 dots are colored. A monochromatic rectangle is defined as a rectangle whose four corners are dots of the array and are all of the same color.
I know this has something to do with the Pigeonhole Principle, but I don't know how to apply it. I also know that in a 3×9 array, there must be at least one monochromatic rectangle. Consider this 3×9 array (with 3 rows and 9 columns). Then in each column of 3 dots, given the 2-coloring arrangement, at least two dots must be the same color by the Pigeonhole Principle.
Secondly, there are $2^3 = 8$ ways a column of 3 dots can be colored. Therefore, with 9 columns, again by the Pigeonhole Principle, at least two of these columns must be colored with the exact same pattern. However, this is only half of the desired monochromatic rectangle, mainly the vertical sides. But because in any vertical array of 3 dots, two of the dots must be colored the same, the horizontal sides of the rectangle are created by connecting these pairs of dots. This completes the monochromatic rectangle.
However, proving the existance of a monochromatic rectangle in this specific 3×9 case is still pretty far off from the desired 8×8 proof. Are there any suggestions on how I can apply a similar logic when approaching a proof for this case?
I appreciate any and all help.
-A
Best Answer
See if the following argument works:
We can assume that the first four dots of the first row are of the same colour, say red. If there is any other row in whose first $4$ dots there are at least $2$ of them are red, then we are done. Otherwise, there are only $5$ possible configurations for the first $4$ dots of the rows, namely $4$ for $1$ red, $3$ blue, $1$ for $0$ red, $4$ blue. Since there are $7$ rows other than the first row, there are two rows which have the same configuration for their first $4$ dots, hence we can derive a monochromatic rectangle from these two rows.