|
|
 |
Условие
Пусть $n$ > 1 – целое число. В одной из клеток бесконечной белой клетчатой доски стоит ладья. Каждым ходом она сдвигается по доске ровно на $n$ клеток по вертикали или по горизонтали, закрашивая пройденные $n$ клеток в чёрный цвет. Сделав несколько таких ходов, не проходя никакую клетку дважды, ладья вернулась в исходную клетку. Чёрные клетки образуют замкнутый контур. Докажите, что число белых клеток внутри этого контура даёт при делении на $n$ остаток 1.Решение
Решение 1. Пусть сторона клеток доски равна 1. Отметим центр начальной клетки и центры всех клеток, до которых ладья может добраться за один или несколько ходов. Проведём через них синие прямые параллельно линиям сетки. Образуется вспомогательная синяя сетка, разбитая на клетки со стороной $n$. Если ладья прыгала из клетки $A$ в клетку $B$, соединим центры этих клеток отрезком. Эти отрезки образуют замкнутый многоугольник; его вершины лежат в узлах синей сетки, а стороны идут по линиям синей сетки. Поэтому площадь многоугольника кратна $n$² (пусть она равна $an$²). Периметр его кратен 2$n$ (ведь шаги ладьи кратны $n$, причём сдвиги ладьи влево компенсируются сдвигами вправо, а сдвиги вверх – сдвигами вниз). Далее можно рассуждать по-разному.
Способ 1. Площадь многоугольника состоит из белой клетчатой части и из чёрной каёмки, окружающей белую часть. Разобьём контур многоугольника на отрезки между узлами синей сетки. К каждому из них изнутри прилегает чёрная прямоугольная полоска ширины ½. Её площадь равна $\frac{n}{2}$. Так как число таких полосок чётно, их общая площадь – целое число, кратное $n$ (пусть $bn$). Но эта «общая площадь» не совпадает с чёрной площадью внутри многоугольника. Несовпадения возникают из-за чёрных клеток в углах многоугольника: если угол равен $90^{\circ}$, то полоски перекрываются по четверти чёрной клетки; а при угле в $270^{\circ}$; внутри остаётся четверть клетки, не покрытая полосками. Внешние углы многоугольника равны $\pm 90^{\circ}$, а поскольку сумма внешних углов (с учётом знаков) равна $360^{\circ}$, то внешних углов в $90^{\circ}$ на 4 больше, чем внешних углов в $-90^{\circ}$, то есть внутренних углов в $90^{\circ}$; на 4 больше, чем углов в $270^{\circ}$. Поэтому площадь чёрной каёмки внутри контура меньше суммарной площади полосок на 1. Значит, чёрная площадь внутри многоугольника равна $bn$ - 1, a белая $an$² - $bn$ + 1. Но эта площадь равна числу белых клеток!
Способ 2. Проведём через центры всех клеток исходной доски красные прямые параллельно линиям сетки, образуется красная сетка с единичными клетками. Многоугольник, рассмотренный выше, – клетчатый многоугольник на этой сетке, поэтому количество Г красных узлов на его границе равно его периметру, а значит, кратно 2$n$. Центром всякой клетки исходной доски является красный узел, поэтому такая клетка целиком лежит внутри этого многоугольника тогда и только тогда, когда внутри этого многоугольника лежит её центр. Поэтому количество $B$ белых клеток внутри многоугольника равно количеству красных узлов внутри него. По формуле Пика для этого многоугольника и красной сетки, $B + \frac{\Gamma}{2} - 1 = an^2$, откуда $B$ ≡ 1 (mod $n$).
Решение 2. Назовём клетки, в которых может останавливаться ладья, узлами. Клетка является узлом, если до какого-то другого узла расстояние как по вертикали, так и по горизонтали кратно $n$. Чёрный контур вместе с белыми клетками внутри него образуют клетчатый многоугольник $M$.
Индукция по периметру $M$. База. Наименьший периметр равен 4($n$ + 1) у квадрата, внутри него находится ($n$ - 1)² белых клеток.
Шаг индукции. Пусть периметр больше 4($n$ + 1).
Способ 1. Тогда найдётся клетчатая вертикаль или горизонталь, содержащая узлы, по обе стороны от которой есть чёрные клетки. Она содержит несколько интервалов внутренних белых клеток с концами в чёрных узлах. Выберем любой из этих интервалов, он разбивает чёрный контур на два контура меньшей длины. По предположению индукции внутри каждого из них число белых клеток сравнимо с 1, а на «разбивающем» интервале сравнимо с -1 по модулю $n$. Поэтому число белых клеток внутри исходного контура сравнимо с 1 + 1 - 1 = 1 (mod $n$).
Способ 2. Многоугольник $M$ имеет выпуклые ($90^{\circ}$) и невыпуклые ($270^{\circ}$) углы. Назовём сторону многоугольника крайней, если она соединяет два равных угла этого многоугольника. Крайние стороны, очевидно, есть, пусть $BC$ – участок пути, соответствующий кратчайшей из них. Без ограничения общности можно считать, что он горизонтален, а ладья пришла в $B$ снизу из ближайшего узла $A$ и ушла из $C$ вниз в ближайший узел $D$ (см. рисунок, где $n$ = 3).
Если из $D$ контур поворачивает в сторону $A$ (или из $A$ в сторону $D$), то $CD$ – крайняя сторона. Значит, $BC = CD$, то есть $ABCD$ – минимальный квадрат, что противоречит рассматриваемому случаю.
В противном случае внутри «отрезка» $AD$ нет других участков пути ладьи: такой участок обязан быть крайним (путь вверх из его концов невозможен), но это противоречит выбору $BC$. Таким образом, все клетки между $A$ и $D$ белые либо все они лежат вне многоугольника. Заменим часть пути $ABCD$ «отрезком» $AB$. При этом многоугольник $M$ потеряет (рис. слева) либо приобретет (рис. справа) белый прямоугольник высоты $n$, то есть количество белых клеток по модулю $n$ не изменится. (На рисунках красные клетки заведомо лежат вне многоугольника, а где лежат жёлтые клетки зависит от того, куда продолжается чёрный контур из точек $A$ и $D$.)
В обоих случаях периметр многоугольника уменьшится, поэтому по предположению индукции число белых клеток в нём сравнимо с 1 по модулю $n$.
