Оценка + пример

Король сделал хода. Поскольку длина каждого хода равна либо единице (прямой ход), либо (диагональный ход), то длина всего пути заведомо не меньше Путь длины изображён на рисунке.

Покажем, что длина пути короля не может быть больше Рассмотрим два соседних выхода A и B короля на границу доски. Если эти граничные поля не соседние, то участок пути короля между ними разбивает доску на две части, в каждой из которых есть целые клетки. Но тогда король не сможет пройти из одной части в другую, что противоречит условию. Значит, поля A и B — соседние и, следовательно, разного цвета. Так как при диагональных ходах цвет поля не меняется, то между каждыми двумя соседними выходами на границу должен быть прямой ход. Поскольку граничных полей то и выходов на границу — тоже и, следовательно, прямолинейных ходов не меньше Следующий рисунок показывает„ что можно обойтись ровно "прямыми"ходами.