ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 78172
Тема:    [ Экстремальные свойства (прочее) ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

Как должна двигаться ладья по шахматной доске, чтобы побывать на каждом поле по одному разу и сделать наименьшее число поворотов?

Решение

Мы будем говорить, что ладья движется вдоль горизонтали (или вертикали), если при своём ходе она перемещается с одного поля этой горизонтали (вертикали) на другое. Допустим, что ладья совершила обход шахматной доски, побывав при этом на каждом поле по одному разу. Покажем, что при обходе доски ладья должна либо хотя бы один раз двигаться вдоль каждой вертикали, либо хотя бы один раз двигаться вдоль каждой горизонтали. Действительно, пусть найдётся вертикаль, вдоль которой ладья ни разу не двигалась. Это значит, что каждое поле этой вертикали (на всех этих полях ладья, по условию, побывала) ладья проходила, двигаясь `` поперёк'' вертикали, т. е. вдоль соответствующей горизонтали. Следовательно, ладья двигалась хотя бы один раз вдоль каждой горизонтали. Пусть, для определённости, ладья двигалась хотя бы один раз вдоль каждой вертикали. На каждую вертикаль (кроме, быть может, той, с которой начинается обход, и той, на которой обход заканчивается) ладья должна войти и после движения вдоль вертикали — выйти с неё. При этом вход и выход осуществляются обязательно с поворотами. Таким образом, общее число поворотов не меньше, чем

6 . 2 + 1 + 1 = 14

(6 вертикалей со "входом" и "выходом", начальная вертикаль только с "выходом", конечная — только со "входом").
Итак, меньше 14 поворотов сделать нельзя. В то же время, обходы, содержащие ровно 14 поворотов, существуют.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 22
Год 1959
вариант
Класс 8
Тур 1
задача
Номер 4
олимпиада
Название Московская математическая олимпиада
год
Номер 22
Год 1959
вариант
Класс 7
Тур 1
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .