По кругу записаны 450 неотрицательных целых чисел, сумма которых равна n. Назовем число удачным, если оба его соседа являются натуральными. Раз в минуту выбирается удачное число, к нему прибавляется 2, а из его соседей вычитается по единице. Процесс заканчивается, если не осталось ни одного удачного числа. Найдите наибольшее значение n, при котором процесс заведомо закончится.
Решение. Начнем с того, что если то процесс необязательно закончится. Действительно, рассмотрим следующую расстановку (мы выписываем числа в строку для удобства, но следует иметь в виду, что первое и последнее число в строке являются соседними на окружности):
Если мы выберем 0 в качестве удачного числа, то получим следующую расстановку
Нетрудно видеть, что она получается из предыдущей сдвигом на одну позицию по часовой стрелке. Проведя такую операцию 450 раз, мы придем в исходную позицию и сможем продолжать процесс бесконечно. При легко строится аналогичный пример.
Докажем теперь, что если то процесс обязательно застопорится. Для этого обратим внимание на нули (хотя бы один ноль обязательно есть, поскольку Нули разбивают окружность на несколько дуг. Одна из них должна быть заполнена единицами, иначе сумма чисел на каждой дуге хотя бы на 1 больше количества чисел в ней, и тогда общая сумма будет не меньше 450. Выберем наименьшую из дуг, заполненных единицами (возможно, это дуга длины ноль, то есть просто два рядом стоящих нуля). Заметим, что длина такой наименьшей дуги не увеличивается при проведении операций, a если проводится операция, затрагивающая эту дугу, то длина строго уменьшается. Действительно, при проведении операции с единицей внутри, дуга разрывается на меньшие части — одну двойку и две дуги, заполненные единицами. При проведении операции с нулем на конце, дуга, очевидно, укорачивается на одну единицу.
Итак, длина наименьшей дуги не увеличивается, и, рано или поздно, она либо сожмется в пару соседних нулей, операции с которыми станут невозможны, либо операций, затрагивающих эту дугу, начиная с некоторого момента проводится не будет.
Если процесс продолжается бесконечно долго, то комбинация чисел по кругу рано или поздно повторится. Пусть повторилась позиция a1, a2, ..., a450, при этом между повторениями число на первой позиции выбирали в качестве удачного x1 раз, число на второй позиции — x2 раз, ..., число на 450-й позиции — x450 раз. Тогда, поскольку все числа после всех операций не изменились, имеют место соотношения
Из них следует, что (достаточно рассмотреть максимальное из xj и понять, что соседние с ним совпадают).
Подведем итог. Зацикливание возможно, только если на каждую позицию приходится ненулевое количество выборов удачного числа. Однако, как мы доказали выше в случае, когда сумма чисел равна 449, появится зона чисел, с которой операции более не проводятся. Это и означает, что процесс будет конечным.
Ответ: 449.
Ответ: 449.