Задача 78172
|
|
 |
Условие
Как должна двигаться ладья по шахматной доске, чтобы побывать на каждом поле по одному разу и сделать наименьшее число поворотов?Решение
Мы будем говорить, что ладья движется вдоль горизонтали (или вертикали), если при своём ходе она перемещается с одного поля этой горизонтали (вертикали) на другое. Допустим, что ладья совершила обход шахматной доски, побывав при этом на каждом поле по одному разу. Покажем, что при обходе доски ладья должна либо хотя бы один раз двигаться вдоль каждой вертикали, либо хотя бы один раз двигаться вдоль каждой горизонтали. Действительно, пусть найдётся вертикаль, вдоль которой ладья ни разу не двигалась. Это значит, что каждое поле этой вертикали (на всех этих полях ладья, по условию, побывала) ладья проходила, двигаясь `` поперёк'' вертикали, т. е. вдоль соответствующей горизонтали. Следовательно, ладья двигалась хотя бы один раз вдоль каждой горизонтали. Пусть, для определённости, ладья двигалась хотя бы один раз вдоль каждой вертикали. На каждую вертикаль (кроме, быть может, той, с которой начинается обход, и той, на которой обход заканчивается) ладья должна войти и после движения вдоль вертикали — выйти с неё. При этом вход и выход осуществляются обязательно с поворотами. Таким образом, общее число поворотов не меньше, чем
6 . 2 + 1 + 1 = 14
(6 вертикалей со "входом" и "выходом", начальная вертикаль только
с "выходом", конечная — только со "входом").
Итак, меньше 14 поворотов сделать нельзя. В то же время, обходы, содержащие ровно 14 поворотов, существуют.
