Задача 109652

Темы:    [ Процессы и операции ] [ Рекуррентные соотношения (прочее) ] [ Инварианты ] [ Индукция (прочее) ]

Сложность: 6+ Классы: 9,10,11

Условие

Автор: Фон-дер-Флаас Д.

На бесконечной в обе стороны полосе из клеток, пронумерованных целыми числами, лежит несколько камней (возможно, по нескольку в одной клетке). Разрешается выполнять следующие действия:

1. Снять по одному камню с клеток n-1 и n и положить один камень в клетку n+1 ;
2. Снять два камня с клетки n и положить по одному камню в клетки n+1 , n-2 .

Докажите, что при любой последовательности действий мы достигнем ситуации, когда указанные действия больше выполнять нельзя, и эта конечная ситуация не зависит от последовательности действий (а зависит только от начальной раскладки камней по клеткам).

Решение

Обозначим через 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' имеем:

Таким образом, для любой конфигурации есть только одна конечная с таким же весом; только к ней и может привести процесс.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1997
Этап
Вариант	5
Класс
Класс	10
задача
Номер	97.5.10.8