MathDB

We call an

n\times n

matrix well groomed if it only contains elements

0

and

1

, and it does not contain the submatrix

\begin{pmatrix} 1& 0\\ 0 & 1 \end{pmatrix}.

Show that there exists a constant

c>0

such that every well groomed,

n\times n

matrix contains a submatrix of size at least

cn\times cn

such that all of the elements of the submatrix are equal. (A well groomed matrix may contain the submatrix

\begin{pmatrix} 0& 1\\ 1 & 0 \end{pmatrix}.

)

3