|
|
 |
Условие
У Вани есть клетчатая бумага двух видов: белая и чёрная. Он вырезает кусок из любой бумаги и наклеивает на серую клетчатую доску $45\times 45$, делая так много раз. Какое минимальное число кусков нужно наклеить, чтобы «раскрасить» клетки доски в шахматном порядке? (Каждый кусок – набор клеток, в котором от любой клетки до любой другой можно пройти, переходя из клетки в соседнюю через их общую сторону. Можно наклеивать куски один поверх другого. Все клетки имеют размер $1\times 1$.)
Решение
Пример. Пусть верхний слой состоит из центральной клетки. Далее пусть каждый нижележащий слой состоит из клеток предыдущего слоя и из клеток, примыкающих к ним по стороне, и имеет противоположный цвет.
Оценка.
Первый способ. Можно считать, что первый наклеенный кусок – весь квадрат, от этого ничего не испортится. Рассмотрим все диагонали, идущие в том же направлении, что и диагональ, идущая из правого верхнего угла в левый нижний. Всего их $89$ (включая угловые клетки-диагонали). Занумеруем их подряд от левого нижнего угла к правому верхнему.
Назовём диагональ готовой, если все её клетки в данный момент имеют тот же цвет, который будет у них в итоге, когда вся доска приобретёт шахматную раскраску.
Будем следить за следующей величиной: количество пар соседних готовых диагоналей (порядок диагоналей в паре не учитываем). Заметим, что в любой такой паре диагонали имеют разный цвет.
Пусть мы наклеили очередной кусок. Рассмотрим диагональ с наименьшим номером $k$, пересекающую этот кусок, и диагональ с наибольшим номером $l$, пересекающую этот кусок. Любая пара соседних диагоналей с номерами от $k$ до $l$ включительно не может быть готовой – они все пересекают новый кусок, а значит, в них найдутся клетки одного и того же цвета. Также не могут образоваться новые пары готовых диагоналей, не пересекающих добавленный кусок. Значит, могут появиться максимум две пары готовых диагоналей: пара $k-1$, $k$ и пара $l$, $l+1$.
После первого хода у нас $0$ пар готовых диагоналей, а в конце – $88$ пар. Так как каждым ходом добавляются максимум две пары, надо сделать ещё минимум $44$ хода, всего $45$ ходов.
Второй способ. Можно считать, что первый наклеенный кусок весь квадрат, от этого ничего не испортится. Считаем его нулевым. Докажем индукцией по $k$ утверждение:
После еще k кусков между любыми двумя клетками есть путь с не более чем 2k сменами цвета.
База при $k = 0$ верна.
Рассмотрим наклеивание $k$-го куска $S$. Пусть до этого между двумя клетками был путь с не более $2(k-1)$ сменами цвета. Если он не заходил в $S$, то он таким и остался. Иначе заменим его кусок от первой его клетки в $S$ до последней такой клетки на путь по $S$ между этими клетками. Тогда количество смен цвета в новом пути увеличилось не более чем на $2$ по сравнению со старым. Переход доказан.
В конце между противоположными углами любой путь имеет хотя бы $88$ смен цвета. Значит, поверх нулевого куска наклеено еще хотя бы $44$.
Третий способ. 1. Пронумеруем все куски в порядке выкладывания.
2. Пройдёмся по кускам от первого номера к последнему. Если встречаем кусок, пересекающийся с одним из предыдущих, то кусок с меньшим номером можем продлить на всю площадь верхнего. Далее начинаем процесс сначала, и так можно добиться, что для любых двух кусков либо нет общих клеток, либо множество клеток одного является подмножеством клеток другого. Выкидываем бессмысленные куски, типа чёрный, лежащий непосредственно на чёрном, или кусок, который в точности накрывает предыдущий.
3. Теперь можем разбить все куски на слои. Первый слой – один кусок. Второй слой – все куски, лежащие непосредственно на первом куске. Третий слой – все куски, лежащие непосредственно на кусках второго слоя, и т. д. Очевидно, цвета кусков будут чередоваться по слоям.
4. Рассмотрим куски второго слоя. Пусть для определённости он белый. Вся непокрытая ими часть первого слоя не будет покрыта уже ничем, поэтому представляет из себя подмножество чёрных клеток шахматной доски. Значит, расстояние между двумя ближайшими клетками двух разных белых кусков – не более $1$ чёрной клетки первого слоя. Если расстояние нулевое, то можем объединить такие два куска – кусков станет меньше, а картинка не изменится. Если расстояние равно одной чёрной клетке, объединим эти два белых куска, добавив между ними одну белую клетку. И добавим один новый чёрный кусок, положив его сверху на эту клетку. Таким образом, итоговая картинка не изменилась, общее количество кусков не изменилось, во втором слое теперь на один белый кусок меньше, а в третьем – на один чёрный кусок больше. Действуя так далее, можем добиться, что во втором слое только один кусок. Далее аналогично (предварительно проведя заново действия 1-3), добиваемся, что в третьем слое – только один кусок, и т.д.
5. Процесс когда-то закончится, так как каждый следующий слой покрывает лишь часть предыдущего. Заметим, что самый верхний кусок может состоять только из одной клетки (на шахматной доске нет двух соседних клеток одного цвета), обозначим эту клетку $К$. Рассмотрим самый дальний от этой клетки угол доски, пусть это левый нижний. Рассмотрим диагонали, идущие слева сверху вправо вниз. Пронумеруем их от дальнего угла до нашей клетки $К$. Так как это самый дальний угол, то $К$ окажется минимум на $45$-й диагонали. Пойдём теперь по слоям сверху вниз. Самый верхний слой заходит не ниже $45$-й диагонали. Каждый следующий слой может зайти своими клетками не более чем на одну новую диагональ (т.к. клетки одного слоя одинакового цвета, а цвета диагоналей чередуются, то «перепрыгнуть» через диагональ противоположного цвета слой не может). Поэтому, чтобы покрыть дальнюю угловую клетку, нужно добавить минимум $44$ слоя. Итого получается $45$ слоёв, то есть требуется минимум $45$ кусков.
Четвёртый способ.
Идея: запустить процесс в обратном порядке и посмотреть, что покрытая часть «разрастается не слишком быстро». И даже проекция на диагональ покрытой части «разрастается не слишком быстро».
Схема решения. Пусть $K_1$, $K_2$, $\dots$, $K_N$ – куски, занумерованные с конца, так что $K_1$ положили последним, $K_2$ – предпоследним, и т.д., $K_N$ – первым. Положим $L_n = K_1\cup K_2\cup\dots\cup K_n$, в частности, $L_N$ – множество всех клеток доски. Ясно, что множество $K_{n+1}\setminus L_n$ не может содержать двух соседних клеток, иначе они после наклеивания в исходном процессе останутся одноцветными. (В частности, $|K_1|=1$.)
Занумеруем подряд $1$, $2$, $\dots$, $(2n-1)$ диагонали одного направления, и пусть $K'_i$ и $L'_i$ – множество номеров диагоналей, пересекающихся с $K_i$ и $L_i$ соответственно. Так как $K_i$ связно, то $K'_i$ – отрезок (то есть подмножество множества $\{1, 2, \dots, (2n-1)\}$, состоящее из нескольких последовательных чисел). Кроме того, $K'_{n+1}\setminus L'_n$ не может содержать двух соседних чисел. Действительно, предположим противное, и $i$, $i+1\in K'_{n+1}\setminus L'_n$. Тогда ломаная, разделяющая $i$-ю и $(i+1)$-ю диагонали, в силу связности $K_{n+1}$, разрезает некоторую доминошку, целиком лежащую в $K_{n+1}$, но ни одна из клеток этой доминошки не принадлежит $L_n$, что противоречит доказанному ранее.
Пусть $L'_i$ состоит из $t_i$ непродолжаемых отрезков. Покажем, что величина $s_n = |L'_n| + t_n$ при переходе от $n$ к $n + 1$ увеличивается не более чем на $2$. Отсюда будет следовать нужная оценка $N\geqslant 45$,так как $s_1=2$ и $s_N =90$.
Пусть $x = |L'_{n+1}|-|L'_n| = |K'_{n+1}\setminus L'_n$, то есть отрезок $K'_{n+1}$ добавляет в $L'_n$ $x$ чисел.
Пусть $x\geqslant 2$. Тогда (так как по доказанному среди этих чисел нет пары соседних чисел) отрезок $K'_{n+1}$ накрывает хотя бы $(x-1)$ отрезков множества $L'_n$, значит, $t_{n+1}\leqslant t_n - x + 2$. Получаем $s_{n+1} = |L'_{n+1}|+t_{n+1} \leqslant (L'_n+x)+(t_n- x+2)=s_n+2$, что и требовалось.
Если же $x = 1$, то, очевидно, $t_{n+1}\leqslant t_n + 1$ и $s_{n+1} = L'_{n+1}+t{n+1} \leqslant (|L'_n|+1)+(t_n+1) = s_n+2$, что и требовалось.
