|
|
 |
Условие
Пусть n > 1 – целое число. В одной из клеток бесконечной белой клетчатой доски стоит ладья. Каждым ходом она сдвигается по доске ровно на n клеток по вертикали или по горизонтали, закрашивая пройденные n клеток в чёрный цвет. Сделав несколько таких ходов, не проходя никакую клетку дважды, ладья вернулась в исходную клетку. Чёрные клетки образуют замкнутый контур. Докажите, что число белых клеток внутри этого контура даёт при делении на n остаток 1.Решение
Решение 1. Пусть сторона клеток доски равна 1. Отметим центр начальной клетки и центры всех клеток, до которых ладья может добраться за один или несколько ходов. Проведём через них синие прямые параллельно линиям сетки. Образуется вспомогательная синяя сетка, разбитая на клетки со стороной n. Если ладья прыгала из клетки A в клетку B, соединим центры этих клеток отрезком. Эти отрезки образуют замкнутый многоугольник; его вершины лежат в узлах синей сетки, а стороны идут по линиям синей сетки. Поэтому площадь многоугольника кратна n² (пусть она равна an²). Периметр его кратен 2n (ведь шаги ладьи кратны 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) = n⋅(an-b)+1. Но эта площадь равна числу белых клеток!
Способ 2. Проведём через центры всех клеток исходной доски красные прямые параллельно линиям сетки, образуется красная сетка с единичными клетками. Многоугольник, рассмотренный выше, – клетчатый многоугольник на этой сетке, поэтому количество Г красных узлов на его границе равно его периметру, а значит, кратно 2n. Центром всякой клетки исходной доски является красный узел, поэтому такая клетка целиком лежит внутри этого многоугольника тогда и только тогда, когда внутри этого многоугольника лежит её центр. Поэтому количество B белых клеток внутри многоугольника равно количеству красных узлов внутри него. По формуле Пика для этого многоугольника и красной сетки, $B + \frac{\Gamma}{2}-1 =an^2$, откуда $B\equiv 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.
