Текст статьиКурдюмов Г. Консервативность бесконечного строя // Квант. — 1979. — № 7. — С. 33—36.
В этой заметке решается задача М500г) из Задачника «Кванта» («Квант», 1978, №4; см. также 1979, №2). В конце заметки приводятся три новые задачи, решения двух из которых (задачи 1 и 3) не известны.
Имеется бесконечная в обе стороны шеренга первоклассников. По команде нале-ВО все первоклассники, кроме конечного их множества, повернулись налево; остальные повернулись направо. В каждую последующую секунду каждый первоклассник поворачивается на $180^\circ$, если первый и третий из стоящих перед ним повёрнуты к нему лицом. Все остальные первоклассники остаются неподвижны. Докажите, что движение в этом бесконечном строю через конечное время прекратится.
Пусть вначале все первоклассники стоят к нам лицом (рис. 1, a). После первого же поворота все они будут смотреть налево или направо. Назовём первоклассников, смотрящих (в данный момент) направо, правыми, смотрящих налево — левыми (рис. 1, б). Очевидно, в первый момент правыми окажутся те, кто правильно выполнил команду «нале-ВО», а «нарушители» окажутся левыми.
Рис. 1
По условию в первый момент левых первоклассников конечное число.
Назовём первоклассников, которые в следующую секунду повернутся, вертунами (легко сообразить, что в каждый момент вертунов конечное число). Левых невертунов мы будем называть злостными. Очевидно, левый первоклассник является злостным, если перед ним на первом или на третьем месте стоит левый первоклассник (рис. 1, в). Вертунов мы будем рисовать зелёным цветом, злостных первоклассников — красным, а правых невертунов — синим (рис. 1, в).
Рис. 2
Прежде чем приводить доказательство в общем виде, рассмотрим для иллюстрации частный случай. Пусть левых первоклассников ровно семь, и все они стоят подряд. Развитие во времени такого строя показано на рисунке 2. Мы видим, что через 12 секунд левых первоклассников не остаётся. Аналогичным образом будет происходить эволюция строя при наличии любого сплошного куска из $n$ левых первоклассников: через $2n-2$ секунд все первоклассники станут правыми, и движение прекратится.
Рис. 3
Приведём теперь доказательство для общего случая — когда левые первоклассники стоят произвольным образом. Нам потребуется несколько дополнительных определений. Назовём островом отрезок, соединяющий самого правого из левых и самого левого из злостных левых. Болотом мы будем называть кратчайший отрезок, примыкающий к острову слева и включающий в себя всех вертунов (болота, конечно, может и не быть). Первоклассников, не вошедших ни в остров, ни в болото, назовём морем (рис. 3).
Лемма 1 (очевидная). Если правее правого первоклассника $A$ стоят только правые первоклассники, то $A$ всегда так и будет правым (рис. 4).
Лемма 2.Если первоклассник $A$ не является злостным и левее его нет злостных, то и в следующую секунду $A$ не будет злостным.
Доказательство. Если $A$ — левый вертун или правый невертун, то через секунду $A$ будет правым и, значит, не будет злостным. Пусть теперь $A$ — правый вертун (рис. 5). Если его сосед слева $A-1$ в исходный момент — правый, то он (сосед) останется правым также и в следующую секунду. Если же первоклассник $A-1$ — левый, то, не будучи злостным, он всё равно повернётся направо. Рассуждения, проведённые для первоклассника $A-1$, проходят и для первоклассника $A-3$, стоящего от $A$ третьим слева. Таким образом, через секунду первоклассники $A-1$ и $A-3$ окажутся правыми. Отсюда следует, что в этот момент $A$ будет левым вертуном.
Рис. 4Рис. 5Рис. 6
Из леммы 2 следует, что если в некоторой момент первоклассник $A$ не является злостным и левее его нет злостных, то $A$ не будет злостным также и во все последующие моменты.
Лемма 3.Если левее злостного первоклассника $A$ нет злостных, то не позднее чем через две секунды $A$ перестанет быть злостным.
Доказательство. Поскольку в исходный момент первоклассник $A$ является злостным и левее него злостных нет, хотя бы один из первоклассников $A-1$ и $A-3$ является левым вертуном. Если среди первоклассников $A-1$, $A-3$ вертун один, то в следующий момент оба первоклассника $A-1$ и $A-3$ уже будут правыми (подумайте, почему) и первоклассник $A$ перестанет быть злостным. То же произойдёт и в случае, когда оба первоклассника $A-1$ и $A-3$ оказываются левыми вертунами. Пусть теперь оба они вертуны, но один из них левый, а другой — правый. Случай, когда первоклассник $A-1$ — левый вертун, а первоклассник $A-3$ — правый, исключается, поскольку тогда первоклассник $A-2$ не может быть ни левым, ни правым (рис. 6, а). Поэтому правый вертун — это первоклассник $A-1$, а левый вертун — первоклассник $A-3$ (рис. 6, б). В этом случае в следующий момент первоклассник $A-1$ становится левым, а первоклассник $A-3$ — правым, причём, как и выше, оба они вертунами стать не могут. Кроме того, поскольку $A-1$ не был злостным с самого начала и левее него злостных не было, он по лемме 2 не будет злостным. Значит, первоклассник $A-1$ — левый вертун, а $A-3$ — правый невертун. Поэтому в следующую секунду первоклассники $A-1$ и $A-3$ оба становятся правыми и первоклассник $A$ перестаёт быть злостным.
Лемма 3 доказана.
Из этих лемм следует, что если $n$ - длина острова (число входящих в него первоклассников), то не более чем через $2n$ секунд остров исчезнет.
Лемма 4.Если среди трёх первоклассников, стоящих подряд, нет злостных левых, а правее их стоят только правее, то через секунду все трое будут правыми невертунами.
Утверждение леммы следует из того факта, что ни один из вышеуказанной тройки первоклассников не может быть правым вертуном (рис. 7).
Итак, после исчезновения острова правая граница болота будет двигаться влево со скоростью не меньше 3. Очевидно, левая его граница не может двигаться влево со скоростью больше 1. Отсюда следует, что длина болота будет уменьшаться (со скоростью не менее 2) и через некоторое время после того, как исчез остров, исчезнет и болото. Все первоклассники станут правыми.
Задача решена. Немного более тонкими рассуждениями можно показать, что движение может продолжаться не более чем $2l+2$ секунд, где $l$ — наибольшее расстояние между двумя левыми первоклассниками после первого поворота (по команде нале-ВО).
3адача 1.Пусть $n$ — количество левых первоклассников после первого поворота. Укажите функцию $f(n)$ такую, что время $t$ движения в строю не может быть больше $f(n)$, однако возможно $t=f(n)$.
Итак, мы нашли такое состояние строя$A_1$ (все первоклассники смотрят вправо), любое конечное изменение которого (т. е. поворот на $180^\circ$ конечного числа первоклассников) исчезнет за конечное время (при эволюции по нашим правилам).
Ясно, что этим свойством обладает и состояние строя $A_2$ «все смотрят влево»: точно так же, как исчезает «остров» в «океане», будет исчезать «озеро» на «материке».
Указанные два состояния строя обладают свойством консервативности: они не меняются со временем, и, какому бы конечному изменению мы их ни подвергли, строй вернётся к исходному состоянию.
Задача 2.Докажите, что других консервативных состояний не существует.
Рассмотрим теперь более общую задачу. Пусть $A$ — некоторое состояние нашего строя (т. е. некоторая бесконечная в обе стороны цепочка символов $\smash{\LARGE\llcorner}$ и $\smash{\LARGE\lrcorner}$). Обозначим через $A(t)$ состояние, в которое строй (при эволюции по нашим правилам) перейдёт через $t$ секунд. Состояния $A$ и $B$ назовём эквивалентными, если со временем они переходят в одно и то же состояние, т. е. если существуют такие $t_1$ и $t_2$, что $A(t_1)=B(t_2)$. Будем говорить, что состояние $A$ иммунно (так сказать, невосприимчиво), если ему эквивалентно любое состояние $A'$, отличающееся от $A$ состояниями лишь конечного числа первоклассников.
Легко видеть, что все состояния, эквивалентные консервативным (в том числе - консервативные), иммуны.
Задача 3.Существуют ли у описанного выше строя имунные состяния, не эквивалентные консервативным?
