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

Проект МЦНМО
при участии
школы 57
Задача 66571
Темы:    [ Замощения костями домино и плитками ]
[ Разрезания, разбиения, покрытия и замощения ]
Сложность: 3
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Из шахматной доски $8\times8$ вырезали 10 клеток. Известно, что среди вырезанных клеток есть как черные, так и белые. Какое наибольшее количество двухклеточных прямоугольников можно после этого гарантированно вырезать из этой доски?

Решение

Каждый двухклеточный прямоугольник содержит чёрную и белую клетки, поэтому если вырезано 9 белых клеток, то больше $32-9=23$ прямоугольников вырезать не получится.

Разрежем доску так, как показано на рис. 1. Вырезанные из доски клетки при разрезании «испортят» не более 10 прямоугольников. Следовательно, у нас уже есть по крайней мере 22 целых прямоугольника. Покажем, как увеличить количество целых прямоугольников на 1. Рассмотрим изображённую на рис. 1 замкнутую цепочку клеток (по цепи идём от клетки a2 вверх). Поскольку вырезаны как белые, так и чёрные клетки, в этой цепи обязательно есть вырезанная белая клетка, за которой идёт вырезанная чёрная клетка. Если эти клетки соседние, то они «портят» только один прямоугольник, значит, при таком разрезании будет не менее 23 целых прямоугольников. В противном случае, если между ними есть ещё клетки, разделим доску между ними так, чтобы новый прямоугольник начинался сразу после вырезанной белой клетки (см. рис. 2). Тогда количество целых прямоугольников увеличится на 1. Следовательно, опять будет не менее 23 целых прямоугольников.


Ответ

23.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 83
Год 2020
класс
Класс 11
задача
Номер 4

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

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