Разделы 
Дополнительно
Задача по математике - 1873
2019-01-21 
На бесконечной в обе стороны полосе из клеток, пронумерованных целыми числами, лежит несколько камней (возможно, по нескольку в одной клетке). Разрешается выполнять следующие действия: 1) Снять по одному камню с клеток $n - 1$ и $n$ и положить один камень в клетку $n +1$. 2) Снять два камня с клетки $n$ и положить по одному камню в клетки $n +1, n - 2$. Докажите, что при любой последовательности действий мы достигнем ситуации, когда указанные действия больше выполнять нельзя, и эта конечная ситуация не зависит от последовательности действий (а зависит только от начальной раскладки камней по клеткам).
Решение:
Обозначим через $a_i$ количество камней в клетке с номером $i$. Тогда последовательность $A = (a_i)$ задает конфигурацию - расположение камней по клеткам. Пусть $\alpha$ - корень уравнения $x^2 = x + 1,$ больший 1. Назовем весом конфигурации $A$ число $w(A) = \sum a_i \alpha^i$. Покажем, что разрешенные действия не меняют веса. Действительно, $\alpha^{n+1} - \alpha^n - \alpha^{n-1} = \alpha^{n-1}( \alpha^2 - \alpha - 1) = 0, \alpha^{n+1} - 2 \alpha^n + \alpha^{n-2} = \alpha^{n-2}( \alpha - 1)( \alpha^2 - \alpha - 1) = 0$.
Докажем индукцией по $k$ - числу камней, что любая последовательность действий завершается. При $k = 1$ это верно. Пусть при числе камней, меньшем $k$, утверждение верно. Рассмотрим процесс, начинающийся с конфигурации $A = (a_i)$ с $\sum a_i = k$. Наибольший номер непустой клетки при разрешенных действиях не уменьшается, но и расти бесконечно он не может - он не может превысить числа $n$, при котором $\alpha^n > w(A)$. Значит, с какого-то момента наибольший номер непустой клетки перестает изменяться, и с камнями, попавшими в эту клетку, уже ничего не происходит. Выбросим эти камни, и применим предположение индукции к оставшимся.
В конечной конфигурации в каждой клетке не более одного камня, и нет двух непустых клеток подряд. Докажем, что любые две конфигурации $A = (a_i)$ и $В = (b_i)$ с такими свойствами имеют разные веса. Пусть $n$ - наибольший номер, при котором $a_i = b_i$; пусть, для определенности, $a_n = 1, b_n = 0$. Выбросим из $A$ и $В$ все камни с номерами, большими $n$ (они в $A$ и $В$ совпадают). Для оставшихся конфигураций $A^{\prime}$ и $В^{\prime}$ имеем:
$w(A^{\prime}) \geq \alpha^n$;
$w(B^{\prime}) < \alpha^{n-1} + \alpha^{n-3} + \alpha^{n-5} + \cdots = \alpha^{n-1} \frac{1}{1 - \alpha^{-2}} = \alpha^n$.
Таким образом, для любой конфигурации есть только одна конечная с таким же весом; только к ней и может привести процесс.
На бесконечной в обе стороны полосе из клеток, пронумерованных целыми числами, лежит несколько камней (возможно, по нескольку в одной клетке). Разрешается выполнять следующие действия: 1) Снять по одному камню с клеток $n - 1$ и $n$ и положить один камень в клетку $n +1$. 2) Снять два камня с клетки $n$ и положить по одному камню в клетки $n +1, n - 2$. Докажите, что при любой последовательности действий мы достигнем ситуации, когда указанные действия больше выполнять нельзя, и эта конечная ситуация не зависит от последовательности действий (а зависит только от начальной раскладки камней по клеткам).
Решение:
Обозначим через $a_i$ количество камней в клетке с номером $i$. Тогда последовательность $A = (a_i)$ задает конфигурацию - расположение камней по клеткам. Пусть $\alpha$ - корень уравнения $x^2 = x + 1,$ больший 1. Назовем весом конфигурации $A$ число $w(A) = \sum a_i \alpha^i$. Покажем, что разрешенные действия не меняют веса. Действительно, $\alpha^{n+1} - \alpha^n - \alpha^{n-1} = \alpha^{n-1}( \alpha^2 - \alpha - 1) = 0, \alpha^{n+1} - 2 \alpha^n + \alpha^{n-2} = \alpha^{n-2}( \alpha - 1)( \alpha^2 - \alpha - 1) = 0$.
Докажем индукцией по $k$ - числу камней, что любая последовательность действий завершается. При $k = 1$ это верно. Пусть при числе камней, меньшем $k$, утверждение верно. Рассмотрим процесс, начинающийся с конфигурации $A = (a_i)$ с $\sum a_i = k$. Наибольший номер непустой клетки при разрешенных действиях не уменьшается, но и расти бесконечно он не может - он не может превысить числа $n$, при котором $\alpha^n > w(A)$. Значит, с какого-то момента наибольший номер непустой клетки перестает изменяться, и с камнями, попавшими в эту клетку, уже ничего не происходит. Выбросим эти камни, и применим предположение индукции к оставшимся.
В конечной конфигурации в каждой клетке не более одного камня, и нет двух непустых клеток подряд. Докажем, что любые две конфигурации $A = (a_i)$ и $В = (b_i)$ с такими свойствами имеют разные веса. Пусть $n$ - наибольший номер, при котором $a_i = b_i$; пусть, для определенности, $a_n = 1, b_n = 0$. Выбросим из $A$ и $В$ все камни с номерами, большими $n$ (они в $A$ и $В$ совпадают). Для оставшихся конфигураций $A^{\prime}$ и $В^{\prime}$ имеем:
$w(A^{\prime}) \geq \alpha^n$;
$w(B^{\prime}) < \alpha^{n-1} + \alpha^{n-3} + \alpha^{n-5} + \cdots = \alpha^{n-1} \frac{1}{1 - \alpha^{-2}} = \alpha^n$.
Таким образом, для любой конфигурации есть только одна конечная с таким же весом; только к ней и может привести процесс.
