|
|
 |
Условие
Шеренга новобранцев стояла лицом к сержанту. По команде "налево"
некоторые повернулись налево, некоторые - направо, а остальные - кругом. Всегда
ли сержант сможет встать в строй так, чтобы с обеих сторон от него оказалось
поровну новобранцев, стоящих к нему лицом?
Решение
Договоримся в случае, когда сержант стоит в строю, обозначать буквой m количество человек, стоящих в строю слева от сержанта к нему лицом, а буквой n - количество человек, стоящих справа от сержанта к нему лицом.Пусть сначала сержант встанет в левый край шеренги. Тогда слева от него
никого не будет (m=0). Если и справа от сержанта никто не будет стоять к
нему лицом (n=0), то задача решена. В противном случае (n>0)
пусть сержант идёт слева направо от человека к человеку. Если он проходит
новобранца, стоявшего к нему спиной, то число m увеличивается на 1, а
число n не изменяется. Если сержант проходит новобранца, стоявшего к нему
лицом, то число n уменьшается на 1, а число m не изменяется. Иначе
оба числа m и n остаются без изменений. Тем самым, число
m-n сначала отрицательно, а в процессе движения сержанта вдоль
строя может увеличиваться не более чем на 1 при прохождении каждого новобранца.
Но когда сержант дойдёт до правого края, уже число n будет нулевым, а
значит, число m-n будет неотрицательным. Итак, начав с
отрицательного числа m-n и прибавляя к нему несколько раз по
единице, мы получили неотрицательное число. Значит, в какой-то момент мы должны
были получить ноль, то есть в тот момент m=n и с обеих сторон от
сержанта лицом к нему находилось поровну новобранцев.
