Задача М500‍‍‍

Мы решим задачи б) и в); задача а) следует из в) (или из б)).

б) Нетрудно видеть, что число поворотов, которые совершит первоклассник $A$‍,‍ не может превосходить общего числа первоклассников $m_A$‍,‍ стоящих к нему лицом (спереди и сзади). Действительно, в те моменты, когда $A$‍‍ не поворачивается, $m_A$‍,‍ очевидно, не меняется, а когда $A$‍‍ поворачивается, $m_A$‍‍ уменьшается на единицу. С другой стороны, очевидно, $m_A\le N-1$‍.‍ Итак, каждый первоклассник может повернуться не более $N-1$‍‍ раз. Простейшие примеры показывают, что эта оценка достигается (рис. 2).

в) Для времени движения справедлива та же оценка: $N-1$‍.‍ Докажем это по индукции. При $N=1$‍,‍ очевидно, оценка выполняется; пусть она выполняется при $N=k$‍.‍ Рассмотрим самого правого (последнего) и второго справа (предпоследнего) первоклассников в строю из $N=k+1$‍‍ человек. Если последний первоклассник смотрит направо, то он, очевидно, поворачиваться не будет, и для времени движения, по предположению индукции, выполняется оценка $k-1$‍.‍ Если последний первоклассник смотрит влево, а предпоследний — вправо, то в следующий момент оба они повернутся, последний первоклассник станет смотреть вправо, а для общего времени движения будет выполняться оценка $1+(k-1)=k=N-1$‍.‍ Остаётся смотреть случай, когда оба — последний и предпоследний — первоклассника смотрят влево.

Будем теперь считать, что первоклассники, стоящие друг к другу лицом, не поворачиваются, а меняются местами (каждый из них делает шаг вперёд); картина от этого не изменится. Тогда нетрудно видеть (рис. 3), что:

1. наличие последнего первоклассника никак не будет сказываться на движении предпоследнего;
2. последний первоклассник может отстать от предпоследнего не более чем на два шага (между ними может стоять не более одного человека).

Из этого следует, что последний (смотрящий влево) первоклассник остановится не более чем через одну секунду после того, как окончательно прекратит движение предпоследний первоклассник (также смотрящий влево); а с остановкой последнего первоклассника движение в строю вообще прекращается (действительно, у него за спиной — только «правые», а перед ним — только «левые»). При этом движение в строю из $N=k+1$‍‍ человек будет продолжаться не более чем на одну секунду больше, чем в строю из $k$‍‍ человек, т. е. не более чем $1+(k-1)=k=N-1$‍‍ секунд. Таким образом, оценка $N-1$‍‍ выполняется. Из рисунка 4 видно, что она является точной (на рисунке $N=6$‍,‍ время движения — пять секунд).

Решение задачи приведено в статье
Курдюмов Г. Консервативность бесконечного строя // Квант. — 1979. — № 7. — С. 33‍—‍36.‍