Задача
Шеренга новобранцев стояла лицом к сержанту. По команде "налево" некоторые повернулись налево, некоторые – направо, а остальные – кругом.
Всегда ли сержант сможет встать в строй так, чтобы с обеих сторон от него оказалось поровну новобранцев, стоящих к нему лицом?
Решение
Для каждого положения сержанта в строю вычислим разность d между количеством человек, стоящих слева от сержанта к нему лицом, и количеством человек, стоящих справа от сержанта к нему лицом. Посмотрим, как это число меняется при сдвиге сержанта на одно место вправо. Если он "проходит" новобранца, стоявшего к нему спиной, то d увеличивается на 1. Если сержант "проходит" новобранца, стоявшего к нему лицом, то d уменьшается на 1. Иначе d не меняется.
Ясно также, что, когда сержант стоит крайним слева, d неположительно, а когда он стоит крайним справа, d неотрицательно. Поскольку на каждом шаге d меняется не более чем на 1, где-то "по дороге" оно примет значение 0. В этом положении с обеих сторон от сержанта лицом к нему находится поровну новобранцев.
Ответ
Всегда.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь