Наткнулась я на эту задачу, пролистывая журнал "Квант" 2000 года. Сразу поняла, что очень хочу показать ее и вам, дорогие читатели)
Формулировка задачи:
Король обошел шахматную доску, побывав на каждом поле. Когда соединили отрезками центры полей, которые он последовательно проходил, получили замкнутую ломаную без самопересечений. Какое наибольшее и какое наименьшее число диагональных ходов мог иметь путь короля?
Напомню, что шахматная доска имеет размер 8x8.
Задачу будем решать элегантным методом "оценка + пример". Он очень часто встречается в интересных олимпиады задачках по математике. Суть в том, чтобы как-то оценить искомую величину (часто довольно грубо), а потом привести конкретный пример, когда такая оценка достигается.
Какое наименьшее число диагональных ходов мог иметь путь короля?
Давайте попробуем оценить. Кажется, что наименьшим числом может быть 0, то есть теоретически король мог вообще не ходить по диагонали. Достигается ли эта оценка? Попробуем привести пример.
Видим, что пример довольно легко нашелся! А значит первая половина задачи решена.
Какое наибольшее число диагональных ходов мог иметь путь короля?
Тут по хорошему нужно каждому читателю взять листок с ручкой и просто попытаться нарисовать путь с наибольшим количеством диагональных ходов. Назовем это "прочувствовать" задачу.
Спустя минут 10 самое лучшее, что у меня получилось, 36 диагональных ходов. Картинку можно увидеть ниже 👇🏽
И тут уже одно из двух: либо у меня не хватило фантазии на большее число ходов, либо это то, чего мы искали.
Ну что же, задача решена?
Если бы все было так просто…)) Теперь осталась самая малость - доказать, что лучше нельзя. И сейчас мы с вами это проделаем, причем довольно элегантным способом.
Доказательство
Раз нам нужно обойти все клетки поля, рассмотрим возможности путей из граничной клетки (А) в другую клетку на границе (В) (без других граничных клеток на пути).
Допустим, клетки А и В не соседние, тогда проведя произвольную ломаную, получим разбиение доски на 2 части. И впоследствии любой путь из одной части в другую ведет к самопересечению пути короля!
Вывод из этого простой: выход на граничные клетки возможен в единственном случае - когда они соседние.
И тут еще одно элегантное замечание!
Соседние граничные клетки А и В - разных цветов. А диагональных ход не меняет цвета клеток
Соответсвенно, между двумя выходами на границу должен быть хотя бы 1 "прямой" ход (для смены цвета клетки поля). Поскольку граничных полей 28, выходов на границу тоже 28, получаем, что «прямых» ходов также не меньше 28.
Так как всего нужно обойти 64 клетки поля и ломаная без самопересечений, число ходов - 64.
Немного магии...
Тогда диагональных ходов не больше чем 64 - 28 = 36 !!!
Задача решена! Для обоих пунктов задачи мы доказали оценку и привели пример, когда она достигается.
Спасибо за внимание!
Другие интересные статьи на моем канале:
Парадокс бесконечного отеля
Дилемма "заключенных". Почему страны воюют, когда мир выгоднее?
Невозможное возможно! 1 + 2 + 3 + 4 + … = -1/12. Правда или математический трюк?