MathDB
Well groomed matrix

Source: Miklós Schweitzer 2018 P3

November 10, 2018
linear algebramatrixcombinatoricscollege contestsMiklos Schweitzer

Problem Statement

We call an n×nn\times n matrix well groomed if it only contains elements 00 and 11, and it does not contain the submatrix (1001).\begin{pmatrix} 1& 0\\ 0 & 1 \end{pmatrix}. Show that there exists a constant c>0c>0 such that every well groomed, n×nn\times n matrix contains a submatrix of size at least cn×cncn\times cn such that all of the elements of the submatrix are equal. (A well groomed matrix may contain the submatrix (0110).\begin{pmatrix} 0& 1\\ 1 & 0 \end{pmatrix}. )
Back to ProblemsView on AoPS