Метка: коридор маршрута

Задача из журнала «Квант» ( 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$.

М.Г.Хованов