Олимпиадная задача по индукции и инвариантам: камни на полосе — 9–11 классы

Обозначим через a_i количество камней в клетке с номером i . Тогда последовательность A=(a_i)задает конфигурацию – расположение камней по клеткам. Пусть α – корень уравнения x²=x+1, больший 1. Назовем весом конфигурации A число w(A)= a_iαⁱ .

Покажем, что разрешенные действия не меняют веса. Действительно, αⁿ⁺1-αⁿ-α^n-1=α^n-1(α²- α-1)=0, αⁿ⁺1-2αⁿ+α^n-2 = α^n-2(α-1)(α²-α-1)=0.

Докажем индукцией по k – числу камней, что любая последовательность действий завершается. При k=1это верно. Пусть при числе камней, меньшем k , утверждение верно. Рассмотрим процесс, начинающийся с конфигурации A=(a_i)с a_i =k . Наибольший номер непустой клетки при разрешенных действиях не уменьшается, но и расти бесконечно он не может – он не может превысить числа n , при котором αⁿ > w(A). Значит, с какого-то момента наибольший номер непустой клетки перестает изменяться, и с камнями, попавшими в эту клетку, уже ничего не происходит. Выбросим эти камни, и применим предположение индукции к оставшимся.

В конечной конфигурации в каждой клетке не более одного камня, и нет двух непустых клеток подряд. Докажем, что любые две конфигурации A=(a_i)и B=(b_i)с такими свойствами имеют разные веса. Пусть n – наибольший номер, при котором a_i= b_i ; пусть, для определенности, a_n=1, b_n=0. Выбросим из A и B все камни с номерами, большими n (они в A и B совпадают). Для оставшихся конфигураций A' и B' имеем: Таким образом, для любой конфигурации есть только одна конечная с таким же весом; только к ней и может привести процесс.

Ответ задачи отсутствует