Решение задачи 277

Условие:

Шеренга новобранцев стоит перед старшиной. Старшина командует: нале-ВО! Но по неопытности часть солдат поворачивается налево, а часть -- направо. После этого каждую секунду происходит вот что: солдаты, оказавшиеся друг к другу лицом, понимают, что произошла ошибка, и оба поворачиваются кругом. Требуется доказать, что рано или поздно повороты прекратятся (при любом числе солдат и при любом их положении после команды).

Решение:

Будем кодировать положения солдат двоичными числами. Длина числа равна количеству солдат в шеренге, если солдат смотрит направо, то он кодируется единицей, если налево, то нулем. Что же происходит с числом, когда пара смотрящих друг на друга солдат поворачиваются кругом? Фрагмент "10" в числе меняется на "01", то есть число уменьшается. Количество двоичных слов определенной длины конечно, значит процесс закончится.