Пример. Обходим доску "змейкой", начиная из нижнего левого угла: вправо до конца, на 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.