|
|
 |
Условие
Дана таблица 4×4 клетки, в некоторых клетках которой поставлено по звёздочке. Показать, что можно так расставить семь звёздочек, что при вычёркивании любых двух строк и любых двух столбцов этой таблицы в оставшихся клетках всегда была бы хотя бы одна звёздочка. Доказать, что если звёздочек меньше, чем семь, то всегда можно так вычеркнуть две строки и два столбца, что все оставшиеся клетки будут пустыми.
Решение
Пусть в таблице расставлено меньше, чем семь звёздочек. Тогда возможны два случая.
1) В какой-то строке (например, в первой) звёздочек нет. Тогда по принципу Дирихле найдётся строка (пусть вторая), в которой расположено не больше двух звёздочек. Вычеркнем из таблицы третью и четвёртую строки, а также столбцы, содержащие звёздочки второй строки. Получившаяся таблица не содержит звёздочек.
2) Во всех строках есть звёздочки. Если бы при этом в трёх строках нашлось по две звёздочки, то число звёздочек в таблице превысило бы 6. Следовательно, найдутся две строки (пусть первая и вторая), в каждой из которых содержится только по одной звёздочке. Вычеркнем третью и четвёртую строки таблицы и те столбцы, в которых стоят звёздочки первой и второй строк. Оставшаяся таблица не содержит звёздочек.
Пример расположения семи звёздочек:
