33
Г. Курдимов
Консервативность бесконечного строй
В этой заметке решается задача М500г) из Заданияка «Кванта» («Квант», 1978, № 4; см. также 1979, № 2). В конце заметки приводятся три новые задачи, решения двух из которых (задачи 1 и 3) не известны.
Имеется бесконечная в обе стороны переклассиков. По команде нале-ВО все переклассики, кроме конечного их множество, повернулись налево; остальные повернулись направо. В каждую последующую секунду каждый переклассик поворачивается на 180°, если первый и третий из стоящих перед ним повернуть к нему лицом. Все остальные переклассики остяются неподвижны. Доказите, что движение в этом бесконечном строй через конечное время прекратится.
Пусть вначале все переклассики стоят к нам лицом (рис. 1, а). После первого же поворота все они будут смотрить налево или направо. Изоведно, в первый момент правыми окажутся те, кто правильно выполнил команду «налево», а «нарушители» окажутсялевыми.
По условияю в первый момент левых переклассиков конечное число.
Изоведем переклассиков, которые в следующую секунду повернуть, вертунами (легко сообщать, что в каждой момент вертунов конечное число). Левых вертунов мы будем называть злостными. Очевидно, левый переклассик является злостным, если перед ним на первом или на третьем месте стоит левый переклассик (рис. 1, в). Вертинов мы будем рисовать зеленьим цветом, злостных переклассиков — красным, а правых вертунов — синым (рис. 1, в).
Прежде чем приводить доказательство в общем виде, рассмотрим для иллюстрации частный случай. Пусть левых переклассиковровно семь, и все они стоят подряд. Развитие во времени такого строя показано на рисунке 2. Мы видим, что через 12 секунд левых переклассиков не остается. Аналогичным образом бу-
Рис. 1.
34
дет пронсходить эволюция строя при наличии любого сплошного куска из n левых первоклассников: через 2n—2 секунд все первоклассники станут правыми, и движение прекраится.
Приведем теперь доказательство для общего случая — когда левые первоклассники стоят произвольным образом. Нам потребуется несколько дополнительных определений. Назовем островом отрезок, соединяющий самого правого из левых и самого ле-
вого из злостных левых. Болотом мы будем называть кратчайший отрезок, примыкающий к острову слева и включаяющий в себя всех вертунов (болота, конечно, может и не быть).
Первоклассников, не вошедших ни в остров, ни в болото, называем морем (рис. 3).
Лемма 1 (очевидная). Если правое правого первоклассника A стоям молко правые первоклассики, то A всегда mak и будем правым (рис. 4).
Рис. 2.
море
болото
остров
море
Рис. 3.