Задача 67435
|
|
 |
Условие
Назовём полоской клетчатый многоугольник, который можно пройти целиком, начав из какой-то его клетки и далее двигаясь только в двух направлениях — вверх или вправо. Несколько таких одинаковых полосок можно вставить друг в друга, сдвигая на вектор (–1, 1). Докажите, что для любой полоски, состоящей из чётного числа клеток, найдётся такое нечётное $k$, что если объединить $k$ таких же полосок, вставив их последовательно друг в друга, то полученный многоугольник можно будет разделить по линиям сетки на две равные части. (На рисунке приведён пример.)Решение 1
Вставим друг в друга достаточно большое количество исходных полосок и пронумеруем их снизу вверх. Расположим новый прямоугольник так, чтобы его левая нижняя клетка совпала с левой нижней клеткой первой полоски. Заметим, что при этом его правая верхняя клетка совпадёт с правой верхней клеткой полоски с номером $a-b$ + 1. Начнём смещать прямоугольник на вектор (&ndash1, 1) до тех пор, пока он полностью не окажется внутри фигуры из полосок (см. рисунок). Такой момент наступит, когда нижний ряд прямоугольника попадёт в горизонталь, в которой будет $a-b$ + 1 клеток. Пусть при этом левая нижняя клетка прямоугольника совпадает с левой нижней клеткой полоски с номером $x$, а правая верхняя – с правой верхней клеткой полоски с номером $y$. Тогда $y - x = a - b$, поэтому числа $x$ и $y$ имеют разную чётность. Оставим $k = x+y$ полосок. Может оказаться, что после этого левая верхняя часть прямоугольника уже не будет находиться внутри фигуры. Исправляем это так: увеличиваем $x$ на 1, то есть смещаем прямоугольник на вектор (–1, 1), при этом $y$ тоже увеличивается на 1, то есть число полосок увеличивается на 2. Если этого не хватило, повторяем процедуру (после каждого шага прямоугольник смещается на одну горизонталь и одну вертикаль, а число полосок увеличивается на 2, поэтому в какой-то момент прямоугольник окажется полностью внутри фигуры).
Докажем, что полученную фигуру можно разрезать по линиям сетки на две равные части. Сделаем разрез по границе исходной полоски, помещенной внутрь нашей фигуры, так, чтобы она осталась целиком в правой нижней части (на нашем рисунке режем вдоль левой и верхней границы красной полоски). Тогда граничный слой клеток в обеих полученных фигурах выглядит так (в левой верхней фигуре делаем обход по часовой стрелке, а в правой нижней – против часовой стрелки):
1) полоска (в левой верхней фигуре это полоска с наибольшим номером, а в правой нижней – наша полоска);
2) лесенка из $x$ ступенек;
3) полоска (в левой верхней фигуре это полоска, получающаяся из нашей полоски смещением на вектор (–1, 1), а в правой нижней – первая полоска);
4) лесенка из $y$ ступенек. Таким образом, полученные фигуры равны.
Решение 2
Будем, считать, что полоска расположена на бесконечной клетчатой (координатной) плоскости. Впишем нашу полоску $\Pi$ в клетчатый прямоугольник $ABCD$ размера $a \times b$ ($AB = a$, $BC = b$). В полоске будет $a + b$ – 1 клетка, поэтому $a + b$ нечётно. Пусть $\Pi$ ограничена слева и сверху ломаной l, идущей из $A$ в $C$ (вправо-вверх).Параллельно перенесём прямоугольник $ABCD$ вместе с полоской $\Pi$ и ломаной $\ell$ на вектор $(- a - b, a + b)$; пусть после переноса мы получили прямоугольник $A'B'C'D'$, вписанную в него полоску $\Pi'$ и ограничивающую ее ломаную l', идущую из $A'$ в $C'$.
Рассмотрим все клетки, лежащие целиком в области, ограниченной ломаными l, l' и отрезками $AA'$, $CC'$. Докажем, что эти клетки образуют искомый клетчатый многоугольник $M$. Во-первых, ясно, что $M$ получается как объединение $k = a+b$ сдвигов полоски $\Pi$ на векторы (–1, 1), (–2, 2), ..., $(-k,k)$.
