На шахматной доске размера $99\times99$ отмечена фигура $\mathit\Phi$ (эта фигура будет разной в пунктах а), б) и в)). В каждой клетке фигуры $\mathit\Phi$ сидит жук. В какой-то момент жуки взлетели и сели снова в клетки той же фигуры $\mathit\Phi$; при этом в одну клетку могло сесть несколько жуков. После перелёта любые два жука, занимавшие соседние клетки, оказались снова в соседних клетках или попали на одну клетку. (Соседними называются клетки, имеющие общую сторону или общую вершину.)
Пусть фигура $\mathit\Phi$ — это «центральный крест», (см. рис. 1). Докажите, что в этом случае какой-то жук вернулся на место либо перелетел в соседнюю клетку.
Верно ли это утверждение, если фигура $\mathit\Phi$ — это «оконная рама», (см. рис. 2)?
Верно ли это утверждение, если фигура $\mathit\Phi$ — это вся доска?
а) Посмотрим, на какую из сторон креста перелетел жук из центральной клетки $O$. Если он остался на месте, то задача решена. Пусть, например, он перелетел вправо, на сторону $OA$ (остальные случаи разбираются так же). Выберем среди жуков, которые сидели на стороне $OA$ и перелетели вправо, жука $X$ — самого далёкого от клетки $O$. Если он отлетел на одну клетку, то задача решена. Если же он отлетел больше чем на одну клетку, то его правый сосед не может перелететь влево (иначе они перестанут быть соседями). Перелететь вправо он также не может, так как $X$ — самый правый жук, перелетевший вправо. Следовательно, правый сосед жука $X$ остался на месте.
Рис. 2Рис. 3
б) В этом случае утверждение неверно. Чтобы показать это, организуем полёт в два этапа. На первом этапе соберём всех жуков на границе правого верхнего квадратика $K$ (см. рис. 3); каждый жук перелетает в ближайшую к нему клетку этого квадратика. При этом соседние жуки не разлетаются и все жуки, сидевшие на границе квадратика $K$, остаются на месте. На втором этапе заставим каждого жука перелететь в противоположную клетку квадратика $K$ (симметричную относительно его центра). Ясно, что при этом соседние жуки также не разлетятся. Докажем, что в результате этих двух перелётов никакой жук не останется на месте и не перелетит в соседнюю клетку. Пусть на первом этапе некоторый жук из клетки $A$ перелетел в клетку $B$, а на втором этапе — в клетку $C$. Так как $C$ лежит на границе $K$, то жук из клетки $C$ после первого этапа останется на месте. Если бы $A$ и $C$ оказались соседними клетками, то жуки, сидевшие в них, перелетели бы после первого этапа в соседние клетки $B$ и $C$. Но $B$ и $C$ — противоположные клетки границы квадратика $K$, и соседями быть не могут. Следовательно, $A$ и $C$ также не являются соседями.
в) В этом случае утверждение верно. При доказательстве будем пользоваться «шахматным» расстоянием между клетками доски: расстоянием между клетками $A$ и $B$ назовём наименьшее число ходов, которое потребуется шахматному королю, чтобы пройти из $A$ в $B$. Из условия задачи вытекает, что расстояния между жуками после перелёта не увеличиваются.
Прямоугольник, составленный из клеток доски, будем называть инвариантным, если любой жук из этого прямоугольника перелетает в клетку этого же прямоугольника. Например, вся доска является инвариантным прямоугольником. Рассмотрим инвариантный прямоугольник с наименьшим числом клеток и докажем, что его размеры, как вертикальный, так и горизонтальный, не превышают двух. Тогда ясно, что любой жук из этого прямоугольника либо останется на месте, либо перелетит в соседнюю клетку.
Предположим противное: наименьший инвариантный прямоугольник $\varPi$ имеет размеры $a\times b$, где $a\ge b$ и $a\gt 2$. Докажем, что в этом случае внутри него можно выбрать ещё меньший инвариантный прямоугольник.
Разберём сначала случай $a\gt b$. Назовём границей прямоугольника две крайние полоски длины $b$, а оставшуюся часть назовём внутренностью (см. рис. 4). Заметим, что расстояние от любой внутренней клетки до любой другой клетки прямоугольника $\varPi$ меньше, чем $a$. Если жуки из всех внутренних клеток перелетели во внутренние клетки, то прямоугольник, составленный из внутренних клеток, будет инвариантным, что и требовалось. Пусть теперь жук из некоторой внутренней клетки $A$ перелетел в граничную клетку $B$. Рассмотрим прямоугольник $M$, составленный из тех клеток прямоугольника $\varPi$, расстояние от которых до клетки $B$ меньше, чем $a$. Поскольку все жуки прямоугольника $\varPi$ находились на расстоянии меньшем чем $a$ от клетки $A$, то все они перелетели в прямоугольник $M$. Поэтому прямоугольник $M$ является инвариантным прямоугольником. Так как он содержит меньше клеток, чем $\varPi$, то и в этом случае всё доказано.
Рис. 4Рис. 5
Осталось разобрать случай $a=b\gt2$. В этом случае границей назовём край этого квадрата, а внутренностью все остальные клетки квадрата (рис. 5). Дальше проходят те же рассуждения, что и выше.
