|
|
 |
Условие
В некоторых клетках квадратной таблицы n×n стоят звёздочки. Известно, что если вычеркнуть любой набор строк (только не все), то найдётся столбец ровно с одной невычеркнутой звёздочкой. (В частности, если строки совсем не вычёркивать, то столбец ровно с одной звёздочкой существует.) Доказать, что если вычеркнуть любой набор столбцов (только не все), то найдётся строка ровно с одной невычеркнутой звёздочкой.
Решение
Заметим, что после перестановки строк и столбцов данной таблицы получаем таблицу, удовлетворяющую условиям задачи. Возьмём столбец с одной звёздочкой (такой существует) и поменяем его с первым столбцом, а также строку, в которой стоит эта звёздочка, поменяем с первой строкой. Затем вычеркнем первую строку и применим утверждение задачи. А после этого переставим строку и столбец со звёздочкой со второй строкой и вторым столбцом. Далее вычеркнем первые две и поступим аналогично. Будем продолжать процесс, пока не упорядочим всю таблицу. Полученная таблица, во-первых, содержит звёздочки на диагонали, а во-вторых, не содержит звёздочек под диагональю. Если теперь вычеркнуть несколько столбцов и номер последнего не вычеркнутого столбца k, то в строчке с номером k ровно одна звёздочка.
