В клетках таблицы 4x4 расставили 6 звёздочек. Всегда ли можно вычеркнуть 2 строки и 2 столбца так, что в оставшихся клетках таблицы звёздочек не будет?

Да, всегда можно.

После вычёркивания \(2\) строк и \(2\) столбцов останется таблица \(2 \times 2\). Нужно показать, что где-то есть такой квадрат \(2 \times 2\) без звёздочек.

Всего клеток \(16\), звёздочек \(6\), значит пустых клеток \(10\). Если бы в каждом квадрате \(2 \times 2\) была звёздочка, то среди пустых клеток не нашлось бы пустого квадрата \(2 \times 2\). Но для таблицы \(4 \times 4\) десяти пустых клеток слишком много: обязательно найдутся две строки и два столбца, на пересечении которых все \(4\) клетки пустые.

Значит, эти две строки и два столбца можно оставить, а остальные \(2\) строки и \(2\) столбца вычеркнуть.

0 0 Пожаловаться