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

Для того чтобы ответить на этот вопрос, давайте внимательно проанализируем условия.

У нас есть квадратная таблица размером 100x100, где некоторые клетки закрашены. Каждая закрашенная клетка должна удовлетворять следующему условию: она либо единственная закрашенная в своем столбце, либо единственная закрашенная в своей строке.

Шаг 1: Разберем условие

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

Иными словами, если в какой-то строке или столбце есть закрашенная клетка, то больше закрашенных клеток в той же строке или столбце быть не может.

Шаг 2: Анализ возможного расположения закрашенных клеток

Пусть рассмотрим, как можно разместить закрашенные клетки с учетом данного условия:

• В каждой строке и в каждом столбце может быть только одна закрашенная клетка. То есть, закрашенные клетки должны располагаться по диагонали, но в разных строках и столбцах.

Шаг 3: Количество клеток, которые могут быть закрашены

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

Шаг 4: Можно ли разместить больше клеток?

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

Ответ

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