|
|
 |
Условие
По доске $n$×$n$ прошла ладья, побывав в каждой клетке один раз, причем каждый её ход был ровно на одну клетку. Клетки занумерованы от 1 до $n^2$ в порядке прохождения ладьи. Пусть $M$ – максимальная разность между номерами соседних (по стороне) клеток. Каково наименьшее возможное значение $M$?
Решение
Пример. Обходим доску "змейкой", начиная из нижнего левого угла: вправо до конца, на 1 вверх, влево до конца, на 1 вверх, ...
Оценка. Способ 1. Предположим противное: $M < 2n$ – 1. Рассмотрим числа верхней строки. Поскольку разность между любыми соседними числами в этой строке не больше 2$n$ – 2, то ладья дошла от меньшего из них к большему, не заходя в нижнюю строку (чтобы достичь её, надо сделать минимум $n$ – 1 ход, и чтобы вернуться – тоже минимум $n$ – 1 ход, плюс ещё один ход делается собственно в нижней строке). Тогда все числа в верхней строке ладья обошла, не заходя в нижнюю строку. Аналогично все числа в нижней строке ладья обошла, не заходя в верхнюю строку. Это значит, что все числа верхней строки больше (или все меньше), чем числа в нижней строке. Аналогично все числа в левом столбце больше (или все меньше) чисел правого столбца. Не теряя общности, можно считать, что числа в левом столбце больше чисел правого, а числа нижней строки больше чисел верхней. Рассмотрим два числа – в левом верхнем углу (число $A$) и в правом нижнем ($B$). С одной стороны, $A > B$ (по столбцам), с другой стороны, $A < B$ (по строкам). Противоречие.
Способ 2. Надо доказать, что найдутся соседние клетки, разность номеров которых не меньше 2$n$ – 1. Пусть доска – это квадрат $ABCD$, этими же буквами обозначим номера соответствующих угловых клеток. Можно считать, что $A$ – наименьший из угловых номеров, а $B < D$. Все клетки при стороне $AD$ разобьются на два непустых множества, в одном номера меньше $B$, а в другом – больше. Найдётся пара соседних по стороне клеток из разных множеств, пусть их номера $X < Y$. Ладье понадобился хотя бы $n - 1$ ход, чтобы добраться от $X$ до стороны $BC$, хотя бы один ход вдоль $BC$ и ещё не менее $n$ – 1 хода, чтобы дойти до $Y$. Поэтому $Y - X \ge 2n$ – 1.
Ответ
2$n$ – 1.
Замечания
8 баллов
