Бинарные матрицы без нулевых и единичных подматриц

[maxal]

Докажите, что во всякой бинарной матрице $5\times 5$ найдётся подматрица $2\times 2$ состоящая целиком из нулей или целиком из единиц.

[neo66]

Если я правильно понял условие, то доказывается несложным анализом. Или предполагалось что-то более остроумное?

[Профессор Снэйп]

neo66 в сообщении #336952 писал(а):

доказывается несложным анализом.

Под анализом подразумевается полный перебор или нечто иное?

-- Сб июл 03, 2010 20:19:01 --

Переходя, при необходимости, от исходной матрицы к инвертированной и переставляя столбцы, будем считать, что первая строка начинается с $000$. Далее, если в первых трёх элементах одной из оставшихся четырёх строк есть два нуля, то всё Ok. Если же нет, то это строки из множества $111??$, $110??$, $101??$, $011??$ и всё опять Ok.

-- Сб июл 03, 2010 20:27:11 --

Тут, наверное, интересней будет оценить минимальное количество подматриц размером $2 \times 2$, состоящих из одинаковых элементов. Потому что существование уж больно просто доказывается.

[maxal]

Профессор Снэйп в сообщении #337051 писал(а):

Тут, наверное, интересней будет оценить минимальное количество подматриц размером $2 \times 2$, состоящих из одинаковых элементов. Потому что существование уж больно просто доказывается.

Да, интересно. Для матрицы $5\times 5$ минимум, равный 2, достигается, например, на матрице:

$$\begin{bmatrix} 0 & 0 & 0 & 1 & 1\\ {\bf 1} & {\bf 1} & 0 & {\bf 1} & 0\\ {\bf 1} & {\bf 1} & 0 & 0 & 1\\ {\bf 1} & 0 & 1 & {\bf 1} & 0\\ 0 & 1 & 1 & 0 & 0 \end{bmatrix}$$

[bot]

(Оффтоп)

Готовлю задачи для олимпиады. Увидал $3\times 7$ и шевельнул её до $5\times 5$, а она, оказывается, тоже была.