ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64542
Темы:    [ Таблицы и турниры (прочее) ]
[ Комбинаторика (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3+
Классы:
В корзину
Прислать комментарий

Условие

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


Решение

  Пример. Закрасим все клетки одной строки и все клетки одного столбца, за исключением их общей клетки. В этом случае условие задачи выполнено и закрашено ровно 198 клеток.
  Оценка. Для каждой закрашенной клетки выделим ту линию (строку или столбец), в которой она единственная закрашенная. При этом не может быть выделено больше 99 строк. Действительно, если выделено 100 строк, то каждая закрашенная клетка – единственная именно в своей строке, но тогда закрашенных клеток – не более 100. Аналогично не может быть выделено и больше 99 столбцов. Поэтому выделенных линий, а значит, и закрашенных клеток, не более чем 198.


Ответ

198.

Источники и прецеденты использования

олимпиада
Название Окружная олимпиада (Москва)
год
Год 2013
класс
Класс 9
задача
Номер 9.4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .