Question

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

Answer 1

Ответ:

да

Пошаговое объяснение:

Возьмём 2 строки с наименьшим количеством звёзд. (Другие 2- вычеркнем.)

Сумма звёзд в них - не больше 2. Потому что, если она бы была больше, то в других 2 строках звёзд не меньше, чем по 2, и сумма всех звёзд вышла бы больше 6.

В выбранных строках вычеркнем 2 столбца, по возможности содержащие звёзды.

Остались пустые 4 клетки.

Answer 2

Нет, это не всегда возможно. Рассмотрим следующий пример:

markdownCopy code
* * * *
* * * *
* * * *
* * * *

В данном случае мы имеем 6 звёздочек, распределённых равномерно по всей таблице. Если мы вычеркнем две строки и два столбца, то останется следующее:

markdownCopy code
* *
* *

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