Самый длинный путь фишки

В маленьком квадрате нельзя посетить три клетки

При каждом ходе число под фишкой увеличивается. Предположим, что в одном квадрате $2\times2$ фишка посетила три клетки: сначала с числом $A$, затем с $B$, затем с $C$. Тогда $A<B<C$. Но любая клетка этого маленького квадрата соседствует со всеми остальными. Поэтому уже из $A$ можно было перейти в $C$. Наиль обязан выбрать число не меньше $C$, и все последующие числа будут ещё больше. Попасть после этого в $B<C$ невозможно. Значит, в одном таком квадрате посещается не больше двух клеток.

Девять маленьких квадратов дают общую границу

Разобьём всё поле на девять непересекающихся квадратов $2\times2$. Каждая клетка принадлежит ровно одному из них. В каждом можно посетить не больше двух клеток, поэтому всего получится не больше $9\cdot2=18$ клеток. Осталось показать, что эту границу можно достичь.

Построим расстановку, достигающую границы

В показанном пути соседние по порядку клетки касаются, а любые две несоседние по порядку — не касаются даже углами. Запишем в начале $1$, дальше вдоль пути — $20,21,\ldots,36$. Остальные клетки заполним числами от $2$ до $19$.

Из клетки с $1$ наибольший сосед — $20$. Затем в любой клетке пути следующий номер больше всех чисел вне пути; все более поздние клетки пути находятся слишком далеко для одного хода. Поэтому фишка последовательно проходит $1,20,21,\ldots,36$ и останавливается. Посещено $1+17=18$ клеток.

Проверить эту расстановку в модели ↑: откройте «Пример из решения». Ваша расстановка сохранится.