Разбиение доски на части
Ошибка.
Попробуйте повторить позже
В клетчатом прямоугольнике 
каждую клетку красят в белый или чёрный цвет. Доминошкой будем называть клетчатый
прямоугольник 
или 
Оказалось, что существует единственный способ разбить данный прямоугольник 
на доминошки
так, чтобы каждая доминошка покрывала хотя бы 1 чёрную клетку. Какое наибольшее количество клеток могло быть покрашено в чёрный
цвет?
Источники:
Подсказка 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.
Пусть прямоугольник 
разбит на доминошки. Двигаясь слева направо, понимаем, что горизонтальные доминошки объединяются в
блоки 
Далее под блоком понимаем такой блок 
из двух горизонтальных доминошек.
Назовём хорошим разбиение на доминошки, в котором в каждой доминошке хотя бы одна клетка чёрная. Назовём раскраску хорошей, если при ней существует ровно одно хорошее разбиение.
1) Приведём пример хорошей раскраски, в которой 120 чёрных клеток. Красим первый столбец белым, следующие 3 столбца — черным, пятый столбец — белым, и далее продолжаем с периодом 5.
Тогда разобьём наш прямоугольник на прямоугольники 
и в каждом из них пусть слева и справа находятся блоки, а посередине —
вертикальная доминошка. Видим, что получено хорошее разбиение.
Покажем, что оно единственно. Посмотрим на границу между 5-м и 6-м столбцами. Эта граница не может находиться внутри блока,
значит, эта граница обязательно должна присутствовать в разбиении и отрезать прямоугольник 
Далее продолжим аналогичные
рассуждения с отрезанием прямоугольников 
Остаётся разобраться, как может быть устроено хорошее разбиение для прямоугольника
В первом столбце не может быть вертикальная доминошка, поэтому в 1-м и 2-м столбцах точно находится блок. Аналогично в 4-м и
5-м столбцах находится вертикальный блок. Тем самым хорошее разбиение однозначно восстановлено. Обоснование того, что наша
раскраска хорошая, завершено.
2) Оценка. Рассмотрим хорошее разбиение прямоугольника 
В каждом блоке не более двух чёрных клеток, иначе мы можем
заменить две горизонтальные доминошки этого блока на вертикальные, и разбиение останется хорошим.
В вертикальной доминошке может быть одна чёрная клетка или две чёрных клетки. В первом случае вертикальную доминошку назовём
светлой, а во втором — тёмной. Если у нас 
тёмных доминошек, то в них 
чёрных клеток, а остальная площадь 
разбита на
блоки и светлые доминошки, т.е. в ней не более половины площади занимают чёрные клетки. Итого чёрных клеток не
более
Остаётся понять, что тёмных доминошек не более 20. Вертикальная доминошка не может граничить с тёмной доминошкой, иначе эту
пару можно заменить на блок (из двух горизонтальных доминошек), и разбиение останется хорошим. Значит, граничить с тёмной
доминошкой может только блок. К одному и тому же блоку слева и справа не могут примыкать две тёмные доминошки, иначе в
образованном ими прямоугольнике 
можно заменить все доминошки на горизонтальные, и разбиение останется хорошим. Рассмотрим
две ближайшие друг к другу тёмные доминошки. Промежуток (по горизонтали) между ними не может составлять 0, 1, 2 или 3
клетки (в последнем случае два блока, соседних с этими тёмными доминошками, должны пересекаться, что невозможно).
Суммируя длины промежутков для 
пар ближайших тёмных доминошек, получаем, что количество вертикалей не
менее
Но оно равно 100. Отсюда 
и 
что невозможно при 
Неравенство 
установлено. Доказательство
оценки завершено.
120
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
