|
|
 |
Условие
На экране компьютера сгенерирована некоторая конечная последовательность нулей и единиц. С ней можно производить следующую операцию: набор цифр "01" заменять на набор цифр "1000". Может ли такой процесс замен продолжаться бесконечно или когда-нибудь он обязательно прекратится?
Решение
Первый способ. Каждую операцию можно понимать как "ход" какой-то единицы: единица меняется местами со стоящим перед нею нулём, а потом после нуля появляются ещё два нуля. Пусть ежеминутно делается один такой ход, и процесс продолжается бесконечно долго. Тогда найдутся единицы, которые "ходили" бесконечное число раз. Рассмотрим самую левую из них и покрасим её в красный цвет. Все единицы левее красной через несколько минут перестанут перемещаться. После этого красная единица каждым своим ходом будет перемещаться ближе к началу последовательности, то есть сделает ещё лишь конечное число ходов, что противоречит её выбору.
Второй способ. Припишем каждому нулю "вес" 4k, где k – количество стоящих правее этого нуля единиц. При указанной операции с единицей, после которой стоит еще k единиц, ноль "веса" 4k+1 заменяется на три нуля "веса" 4k. Суммарный "вес" всех нулей при этом уменьшается. Так как суммарный "вес" всех нулей – целое неотрицательное число, процесс не может продолжаться бесконечно.
Ответ
Процесс прекратится.
