Lets say each square of a $3\times9$ rectangular board is colored either blue or red. How can I prove mathematically that for any such coloring, the board will always contain a subrectangle (paralell to the original one) whose four corners are the same color?
I have a feeling it has something to do with $3^2 = 9$, therefore a $3\times9$ rectangle would have this be true where a 3×6 triangle would not because $3^2 \neq 6$. I'm not sure if that's even remotely correct – just a hunch.
I'm also thinking about the fact that each of the $27$ squares is a rectangle itself, therefore, you would always end up with one of those squares having each of its four corners are the same color.
I know this involves the pigeonhole principle, but I'm just not sure how to "prove" it. Any tips in the right direction?
Best Answer
So there are $9$ columns and $3$ rows of duo-colored squares. For each column of $3$ squares there are $2^3=8$ possible combinations. So by the pigeonhole principle there must be $2$ columns that have the same combination. And for each of these $2$ columns, there must be two squares that have the same color. So you can find the required rectangle now.
EDIT:
I think the minimal number of columns is $7$. Each column must contain two squares of the same color. Suppose the two colors are R and B, then the possible positions are:
$$ \mbox{RR*,R*R,*RR,BB*，B*B,*BB} $$
where the * means any color.
So if there are more than $6$(greater than or equal to $7$) colomuns then one of the above $6$ positions must repeat and then create a rectangle with same color.
And a $6$-column counter-example is obvious from the discussion above:
$$\begin{matrix} \mathrm{\color{Red}R} & \mathrm{\color{Blue}B} & \mathrm{\color{Blue}B} & \mathrm{\color{Red}R} & \mathrm{\color{Red}R} & \mathrm{\color{Blue}B} \\ \mathrm{\color{Blue}B} & \mathrm{\color{Red}R} & \mathrm{\color{Blue}B} & \mathrm{\color{Red}R} & \mathrm{\color{Blue}B} & \mathrm{\color{Red}R} \\ \mathrm{\color{Blue}B} & \mathrm{\color{Blue}B} & \mathrm{\color{Red}R} & \mathrm{\color{Blue}B} & \mathrm{\color{Red}R} & \mathrm{\color{Red}R} \end{matrix}$$