|
|
 |
Условие
На бесконечной в обе стороны полосе из клеток, пронумерованных целыми числами, лежит несколько камней (возможно, по нескольку в одной клетке). Разрешается выполнять следующие действия:
- Снять по одному камню с клеток n-1 и n и положить один камень в клетку n+1 ;
- Снять два камня с клетки n и положить по одному камню в клетки n+1 , n-2 .
Решение
Обозначим через ai количество камней в клетке с номером i .
Тогда последовательность A=(ai) задает конфигурацию –
расположение камней по клеткам.
Пусть α – корень уравнения x2=x+1 , больший 1.
Назовем весом конфигурации A число w(A)= aiαi .
Покажем, что разрешенные действия не меняют веса. Действительно,
αn+1-αn-αn-1=αn-1(α2-
α-1)=0 ,
αn+1-2αn+αn-2 =
αn-2(α-1)(α2-α-1)=0 .
Докажем индукцией по k – числу камней, что любая
последовательность действий завершается. При k=1 это верно. Пусть
при числе камней, меньшем k , утверждение верно.
Рассмотрим процесс, начинающийся с конфигурации A=(ai) с ai =k .
Наибольший номер непустой клетки при разрешенных действиях не уменьшается,
но и расти бесконечно он не может – он не может превысить числа n , при
котором αn > w(A) . Значит, с какого-то момента наибольший номер
непустой клетки перестает изменяться, и с камнями, попавшими в эту клетку,
уже ничего не происходит. Выбросим эти камни, и применим предположение
индукции к оставшимся.
В конечной конфигурации в каждой клетке не более одного камня, и нет
двух непустых клеток подряд. Докажем, что любые две конфигурации A=(ai)
и B=(bi) с такими свойствами имеют разные веса. Пусть n –
наибольший номер, при котором ai= bi ; пусть, для определенности, an=1 ,
bn=0 . Выбросим из A и B все камни с номерами, большими n (они
в A и B совпадают). Для оставшихся конфигураций A' и
B' имеем:
Таким образом, для любой конфигурации есть только одна конечная с
таким же весом; только к ней и может привести процесс.
