Show that there is a $6$ x $4$ board whose squares are all black or white, where no rectangle has the four vertex squares of the same color. Also show that on each $7$ x $4$ board whose squares are all black or white, there is always a rectangle whose four vertex squares are the same color. Point: On the board, adjacent houses do not necessarily have different colors.
I suspect it involves Pigeonhole principle or something discrete-mathematics, but I don't know how to solve it
For the first part, the following construction seems to work: $$\begin{matrix} 0&0&1&1&1&0\\1&1&0&0&1&0\\1&0&1&0&0&1\\0&1&0&1&0&1 \end{matrix}$$ Here, $1$ and $0$ stand for black and white respectively. For the $7\times 4$ case, let's assume such a configuration exists and derive a contradiction. Consider the possible configurations of the first two rows. In each column, they must be either $$\begin{bmatrix}1\\1\end{bmatrix},\begin{bmatrix}0\\0\end{bmatrix},\begin{bmatrix}1\\0\end{bmatrix}\text{ or}\begin{bmatrix}0\\1\end{bmatrix}.$$ There are six columns to fill in. If we were to choose $2$ or more of either $\begin{bmatrix}1\\1\end{bmatrix}$ or $\begin{bmatrix}0\\0\end{bmatrix}$, then the construction fails since the rectangle with these two columns as vertices in the first two rows fails the condition. Furthermore, if we were to choose $3$ or more of either $\begin{bmatrix}1\\0\end{bmatrix}$ or $\begin{bmatrix}0\\1\end{bmatrix}$, then the construction fails as well: for convnience if we assume these three are arranged in the three leftmost columns, then the entry in the third row and first column can be neither $0$ or $1$. If it is $0$, then the entries in the third row and second column, and the third row and third column, must be forced to be $1$, which causes the condition to fail considering the rectangle with vertices being the second and third columns in the first and third rows respectively. The case for the entry being $1$ is similar.
Below is an example for illustration. $$\begin{bmatrix}1&{\color{red}1}&{\color{red}1}\\0&0&0\\0&{\color{red}1}&{\color{red}1}\end{bmatrix}$$
Therefore, we have concluded that we can choose at most $1$ of $\begin{bmatrix}1\\1\end{bmatrix}$ and $\begin{bmatrix}0\\0\end{bmatrix}$ each, and at most $2$ of $\begin{bmatrix}1\\0\end{bmatrix}$ and $\begin{bmatrix}0\\1\end{bmatrix}$ each. So we can fill up at most $1+1+2+2=6$ columns, contradicting the assumption that we can fill up $7$.
Let's say the rows are $4$ wide, and let's try and get as many columns while avoiding the unicolor-vertex-square. Now, if there is a row with $4$ black squares, then the other rows can have at most $1$ other black square. But that means that two of those other rows will have at least $2$ white squares in the same columns, and so you cannot have any row with $4$ black squares, and by symmetry no row with $4$ white squares either if you want at least $4$ columns.
If the first row has $3$ black squares, then no other rows can have $3$ black squares. Likewise, you can have at most $1$ row with $3$ white squares. All other rows must therefore have $2$ black and $2$ white squares.
