монохроматическая подматрица

Сообщение №9061 от Вася 01 ноября 2003 г. 21:39
Тема: монохроматическая подматрица

дана матрица размером н*н
все её элементы это 0 или 1


доказать, что всегда можно получить подматрицу размером лог(н)*лог(н) все элементы которой равны

подматрица получается путем выбора лог (н) строк и столбцов - элементами их пересечений


Отклики на это сообщение:

> дана матрица размером н*н
> все её элементы это 0 или 1
> доказать, что всегда можно получить подматрицу размером лог(н)*лог(н) все элементы которой равны
> подматрица получается путем выбора лог (н) строк и столбцов - элементами их пересечений

Контр-пример: н=4, лог(н)=2
матрица

1100
0011
0110
1001

не содержит монохроматической подматрицы размера 2x2.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100