|
|
 |
Условие
На кольцевой дороге через равные промежутки расположены 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
