Тема . Клетчатые задачи

Разбиение доски на части

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела клетчатые задачи
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#125860

В клетчатом прямоугольнике 2× 100  каждую клетку красят в белый или чёрный цвет. Доминошкой будем называть клетчатый прямоугольник 1× 2  или 2×1.  Оказалось, что существует единственный способ разбить данный прямоугольник 2× 100  на доминошки так, чтобы каждая доминошка покрывала хотя бы 1 чёрную клетку. Какое наибольшее количество клеток могло быть покрашено в чёрный цвет?

Источники: Всеросс, РЭ, 2025, 10.8 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Для оценки введём следующие термины: блок — две соседние горизонтальные доминошки, тёмная доминошка — доминошка с 2 черными клетками, светлая — с одной. Что можно сказать про блок в контексте условия задачи?

Подсказка 2:

В блоке не более двух черных клеток, иначе этот блок можно по-разному замостить двумя доминошками. Пусть имеется k тёмных доминошкек. Остальные 200 - 2k приходятся на блоки и светлые доминошки. Как можно оценить количество черных клеток среди них?

Подсказка 3:

Не более половины, потому что в каждой светлой доминошке и блоке не более половины клеток черные. Значит, всего черных клеток не больше 2k + (100 - k) = 100 + k. Таким образом, все свелось к оцениванию количества темных доминошкек.

Подсказка 4:

Чтобы его оценить, давайте поймём, с какими фигурами они могут граничить. Может ли вертикальная доминошка граничить с тёмной?

Подсказка 5:

Нет, ведь тогда их можно заменить на блок. Значит, тёмная доминошка может граничить только с блоком. Может ли к одному блоку примыкать несколько таких доминошкек подряд?

Подсказка 6:

Нет, ведь тогда их можно заменить на две горизонтальные. Какое минимальное количество клеток по горизонтали может быть между двумя соседними тёмными доминошками? Может ли оно быть менее 4?

Подсказка 7:

Используя эту информацию, можно оценить снизу количество вертикалей некоторым выражением от k. Учитывая, что вертикалей 100, получится оценка на k.

Подсказка 8:

Итак, скорее всего, вы получили, что вертикалей хотя бы 5k - 4, откуда получается оценка на 20 тёмных доминошек. Осталось придумать пример. Для удобства попробуйте разбить доску на большое количество одинаковых маленьких объектов. Например, в контексте задачи удобно работать с прямоугольником 2×5.

Показать ответ и решение

Пусть прямоугольник 2× 100  разбит на доминошки. Двигаясь слева направо, понимаем, что горизонтальные доминошки объединяются в блоки 2× 2.  Далее под блоком понимаем такой блок 2× 2  из двух горизонтальных доминошек.

Назовём хорошим разбиение на доминошки, в котором в каждой доминошке хотя бы одна клетка чёрная. Назовём раскраску хорошей, если при ней существует ровно одно хорошее разбиение.

1) Приведём пример хорошей раскраски, в которой 120 чёрных клеток. Красим первый столбец белым, следующие 3 столбца — черным, пятый столбец — белым, и далее продолжаем с периодом 5.

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

Покажем, что оно единственно. Посмотрим на границу между 5-м и 6-м столбцами. Эта граница не может находиться внутри блока, значит, эта граница обязательно должна присутствовать в разбиении и отрезать прямоугольник 2× 5.  Далее продолжим аналогичные рассуждения с отрезанием прямоугольников 2× 5.  Остаётся разобраться, как может быть устроено хорошее разбиение для прямоугольника 2× 5.  В первом столбце не может быть вертикальная доминошка, поэтому в 1-м и 2-м столбцах точно находится блок. Аналогично в 4-м и 5-м столбцах находится вертикальный блок. Тем самым хорошее разбиение однозначно восстановлено. Обоснование того, что наша раскраска хорошая, завершено.

2) Оценка. Рассмотрим хорошее разбиение прямоугольника 2×100.  В каждом блоке не более двух чёрных клеток, иначе мы можем заменить две горизонтальные доминошки этого блока на вертикальные, и разбиение останется хорошим.

В вертикальной доминошке может быть одна чёрная клетка или две чёрных клетки. В первом случае вертикальную доминошку назовём светлой, а во втором — тёмной. Если у нас k  тёмных доминошек, то в них 2k  чёрных клеток, а остальная площадь (200− 2k)  разбита на блоки и светлые доминошки, т.е. в ней не более половины площади занимают чёрные клетки. Итого чёрных клеток не более

2k+ (100 − k)= 100 +k.

Остаётся понять, что тёмных доминошек не более 20. Вертикальная доминошка не может граничить с тёмной доминошкой, иначе эту пару можно заменить на блок (из двух горизонтальных доминошек), и разбиение останется хорошим. Значит, граничить с тёмной доминошкой может только блок. К одному и тому же блоку слева и справа не могут примыкать две тёмные доминошки, иначе в образованном ими прямоугольнике 2× 4  можно заменить все доминошки на горизонтальные, и разбиение останется хорошим. Рассмотрим две ближайшие друг к другу тёмные доминошки. Промежуток (по горизонтали) между ними не может составлять 0, 1, 2 или 3 клетки (в последнем случае два блока, соседних с этими тёмными доминошками, должны пересекаться, что невозможно). Суммируя длины промежутков для k− 1  пар ближайших тёмных доминошек, получаем, что количество вертикалей не менее

k+4(k− 1)=5k− 4.

Но оно равно 100. Отсюда 5k − 4≤ 100  и 5k ≤104,  что невозможно при k ≥21.  Неравенство k≤ 20  установлено. Доказательство оценки завершено.

Ответ:

120

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!