The question was asked in my today's quiz and I have no idea how to start with it. It's evident that we have to use pigeonhole principle somehow but how I am not getting. Question is " A 4×9 rectangular board is divided into squares each of which is coloured red or green or blue. Prove that the board contains a rectangle whose four corner squares are all the same colour. Thanks.
Tricky problem on pigeonhole principle
pigeonhole-principle
Related Solutions
Imagine the following array: $$\begin{array}[cccccccccc] .1 && 2 && 3 && 4 && \ldots && n-2 && n-1 && n \\ 2n && 2n-1 && 2n-2 && 2n-3 && \ldots && n+3 && n+2 && n+1\end{array}$$
Notice that each column sums to $2n+1$ and all of the numbers from $1$ to $2n$ are used in the array. There are $n$ columns. What you want to prove is that if you were to highlight $n+1$ numbers in this array (i.e. the elements of $T$), there would be a whole column highlighted, and that pair would sum to $2n+1$.
The pidgeonhole principle essentially says that we cannot possibly highlight $n+1$ numbers such that no two lie in the same column, if there are but $n$ columns. If you want to see this, then just take a small array, like for $n=3$: $$\begin{array}.1 && 2 && 3\\6 && 5 && 4\end{array}$$ Now, let's start highlighting some numbers, trying to avoid putting two in a column. Our goal is to highlight $4$ numbers, as that is the size of the set $T$. We could start by putting $1$ in $T$: $$\begin{array}.\color{red}1 && 2 && 3\\6 && 5 && 4\end{array}$$ but now we know we can't put $6$ in $T$ too, because that would sum to $2n+1$. So we might choose $5$ as our next number, forbidding $2$ and we might choose $4$ as the number after that: $$\begin{array}.\color{red}1 && 2 && 3\\6 && \color{red}5 && \color{red}4\end{array}$$
So, now we have a highlighted number in every column- and adding any further number to the set $T$ would create a pair summing to $7$. But this means that we can't have a fourth element in $T$, at least given how we started - and the pidgeonhole principle guarantees that we can never choose a set of size $4$ without putting two elements in one column.
The key point here is that we should imagine that, as we're creating $T$, we're not choosing numbers to put in it, we're choosing which column to take the numbers from. There are $n$ columns, and we need to make $n+1$ choices - thus we will, at some point, choose the same column twice, and in this context, that means we need to have both elements of some column in $T$, and this forms a pair summing to $2n+1$.
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}$$
Best Answer
Counter Example ... for instance ...