Question

В квадратной таблице размером 100×100 некоторые клетки закрашены. Каждая закрашенная клетка является единственной закрашенной клеткой либо в своем столбце, либо в своей строке. Какое наибольшее количество клеток может быть закрашено?

Answer 1

100 закрашенных клеток

Answer 2

Рассмотрим случай, когда в каждом столбце ровно одна закрашенная клетка. В этом случае мы можем закрасить не более 100 клеток.

Однако, если есть столбец, в котором более одной закрашенной клетки, то мы можем выбрать только одну из них, так как в противном случае в этом столбце не будет ни одной незакрашенной клетки, которую мы могли бы использовать для закрашивания в других строках. Таким образом, мы можем закрасить не более, чем 100 клеток.

Теперь рассмотрим случай, когда в каждой строке ровно одна закрашенная клетка. Аналогично предыдущему случаю, мы можем закрасить не более 100 клеток.

Наконец, если есть строка, в которой более одной закрашенной клетки, то мы можем выбрать только одну из них, так как в противном случае в этой строке не будет ни одной незакрашенной клетки, которую мы могли бы использовать для закрашивания в других столбцах. Таким образом, мы можем закрасить не более, чем 100 клеток.

Итак, в любом случае мы можем закрасить не более 100 клеток. Это максимальное возможное количество закрашенных клеток в такой таблице.