Задача из журнала «Квант» ( 1989 год, №3).
Какое наибольшее число поворотов может содержать замкнутый маршрут ладьи, обходящей по одному разу все клетки шахматной доски $ 8 \times 8 $ клеток?
Решение
Ответ: $56$ поворотов. Маршрут с $56$ поворотами показан на рисунке 1.
Докажем, что это число нельзя превысить.
Доказательство
Назовем клетку доски коридором для данного маршрута, если в ней ладья не делает поворота. Заметим, что из каждой пары клеток, смежных с угловыми, хотя бы одна является коридором — иначе в клетке, соседней с соответствующей угловой по диагонали, ладья побывает дважды (рис.2).
Разобьем доску на $4$ квадрата $4 \times 4$. В каждом из них есть коридор, соседний с угловой клеткой. Покажем, что кроме него есть еще хотя бы один коридор. Рассмотрим, например, левый нижний квадрат (рис.3) и допустим, что клетка $a2$ — коридор.
Предположим, что других коридоров в этом квадрате нет. Тогда, очевидно, что маршрут будет последовательно проходить по клеткам $b2$, $b1$, $a1$, $a2$, $a3$, $b3$, $b4$. Следующей будет клетка $а4$, иначе мы в нее никогда не попадем (или маршрут не замкнется). Теперь можно аналогично продолжить маршрут в другую сторону $b2$, $c2$, $c1$, $d1$, $d2$, $e2$. Из полученного рисунка видно, что маршрут должен содержать участок $d3$, $c3$, $c4$, следовательно одна из клеток — $d3$ или $с4$ — коридор (это доказывается также, как для угловых клеток — см. начало решения).
Итак, число коридоров не меньше $ 2 \times 4 = 8 $, а число поворотов — не больше $ 64 — 8 = 56 $.
М.Г.Хованов