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

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

Условие

На кольцевой дороге через равные промежутки расположены 25 постов, на каждом стоит полицейский. Полицейские пронумерованы в каком-то порядке числами от 1 до 25. Требуется, чтобы они перешли по дороге так, чтобы снова на каждом посту был полицейский, но по часовой стрелке за номером 1 стоял номер 2, за номером 2 стоял номер 3, ..., за номером 25 стоял номер 1. Докажите, что если организовать переход так, чтобы суммарное пройденное расстояние было наименьшим, то кто-то из полицейских останется на своём посту.


Решение

Будем считать, что длина дороги равна 25. Пусть при переходе от исходной расстановки A в некоторую "упорядоченную" расстановку B каждый из полицейских переместился (разумеется, каждый из них двигался по меньшей дуге, соединяющей его исходное положение с новым). Докажем, что суммарное пройденное расстояние можно уменьшить. Не менее 13 полицейских шли на новое место в одном направлении (пусть по часовой стрелке). Рассмотрим расстановку C, получающуюся из B сдвигом на одно место против часовой стрелки. Теперь при переходе из A в C как минимум у 13 полицейских пройденные расстояния уменьшились на 1, а у остальных, если и увеличились, то не больше чем на 1. В результате суммарное расстояние уменьшилось как минимум на 1.

Замечания

баллы: 8-9 кл – 7, 10-11 кл – 6

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

олимпиада
Название Турнир городов
Турнир
Номер 36
Дата 2014/15
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 4
олимпиада
Название Турнир городов
Турнир
Номер 36
Дата 2014/15
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 2

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

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