Условие
В углах шахматной доски 3 на 3 стоят кони: в верхних углах — белые, в
нижних — чёрные. Доказать, что для того, чтобы им поменяться местами,
потребуется не менее 16 ходов. (Кони не обязательно ходят сначала белый,
потом чёрный. Ходом считается ход одного коня.)
Решение
рис.
Занумеруем поля доски (кроме центрального) в порядке обхода их шахматным
конём (рис. 40, а); белые кони стоят на полях 1 и 3, чёрные — на полях
5 и 7. Рассмотрим вспомогательную схему, изображённую на рис. 40, б.
Положения коней обозначены символами:
o — белый конь,
× — чёрный конь.
Ход коня изображается на схеме движением одного из символов на один шаг по
или против часовой стрелки.
Заметим, что после всех перестановок каждый конь сделает чётное число ходов
(так как после одного хода меняется цвет поля, на котором стоит конь, а все
поля 1, 3, 5, 7 — одного цвета).
Пусть какой-то конь сделал за все время перестановок только 2 хода; например,
пусть белый конь 1 встал на поле 7, пройдя через поле 8.
Так как при этом белый конь 3 должен встать на поле 5, а чёрный конь 5 на
одно из полей 1 или 3, то эти два коня должны на схеме `` перескочить''
один через другого или через коня, стоящего вначале на поле 1. Но такое ``
перескакивание'' означает, что при каком-то ходе в одной клетке будут
находиться сразу два коня, что противоречит правилам.
Итак, ни один конь не может сделать только 2 хода. Это значит (ввиду чётности
числа ходов каждого коня), что всего будет сделано не меньше, чем
4
. 4 = 16 ходов.
Источники и прецеденты использования
