51-я Международная Математическая OлимпиадаКазахстан, Астана, 2010 год

В каждой из шести коробок ${{B}_{1}}$, ${{B}_{2}}$, ${{B}_{3}}$, ${{B}_{4}}$, ${{B}_{5}}$, ${{B}_{6}}$ изначально находится ровно по одной монете. Разрешается производить операции следующих двух типов:
Тип 1: Выбрать любую непустую коробку ${{B}_{j}}$, где $1\le j\le 5$, убрать из нее одну монету, и добавить две монеты в коробку ${{B}_{j+1}}$.
Тип 2: Выбрать любую непустую коробку ${{B}_{k}}$, где $1\le k\le 4$, убрать из нее одну монету, и поменять местами содержимое (возможно пустое) коробки ${{B}_{k+1}}$ с содержимым (возможно пустым) коробки ${{B}_{k+2}}$.
Существует ли конечная последовательность таких операций, приводящая к ситуации, в которой коробки ${{B}_{1}}$, ${{B}_{2}}$, ${{B}_{3}}$, ${{B}_{4}}$, ${{B}_{5}}$ пусты, а в коробке ${{B}_{6}}$ находится ровно ${{2010}^{{{2010}^{2010}}}}$ монет? (По определению ${{a}^{{{b}^{c}}}}={{a}^{({{b}^{c}})}}$.)

Комментарий/решение

Покажем, что такая последовательность операций существует. Пусть набор $(a_1, a_2, \ldots , a_n)$ показывает количества монет в каких-то $n$ последовательных коробках. Заметим, что из позиции $(n, 0, 0)$ можно получить позицию $(0, 2^n, 0)$ следующим образом: $$(n, 0, 0) \rightarrow (n-1, 2, 0) \rightarrow (n-1, 0, 2^2) \rightarrow (n-2, 2^2, 0) \rightarrow (n-2, 0, 2^3) \rightarrow (n-3, 2^3, 0) \rightarrow \ldots \rightarrow (0, 2^n, 0).$$

Тогда выходит, что из позиции $(n, m, 0, 0)$ можно получить позицию $(n-1, 2^m, 0, 0)$ так $(n, m, 0, 0) \rightarrow (n, 0, 2^m, 0) \rightarrow (n-1, 2^m, 0, 0).$ Теперь сделаем следющие операции: $$ (1, 1, 1, 1, 1, 1) \rightarrow (0, 3, 1, 1, 1, 1) \rightarrow (0,1, 5, 1, 1, 1) \rightarrow (0, 1, 1, 9, 1, 1) \rightarrow (0, 1, 1, 1, 17, 1) \rightarrow (0, 1, 1, 1, 0, 35) \rightarrow (0, 1, 1, 0, 35, 0) \rightarrow (0, 1, 0, 35, 0, 0) \rightarrow (0, 0, 35, 0, 0, 0) \rightarrow (0, 0, 34, 2, 0, 0) \rightarrow (0, 0, 33, 4, 0, 0) \rightarrow (0, 0, 32, 16, 0, 0) \rightarrow (0, 0, 31, 65536, 0, 0) \rightarrow \ldots \rightarrow (0, 0, 0, X, 0, 0). $$

Определим число $X$ через последовательность $\left\{ x_n \right\}:$ $x_1 = 2, x_{n+1} = 2^{x_n}$ для всех натуральных $n$. Тогда $X = x_{35}$. Заметим, что $Y = 2010^{2010^{2010}}$ делится на $4$, то есть можно переписать $Y = 4Z$. Очевидно, что $(0, 0, 0, 0, 0, Y) = (0, 0, 0, 0, 0, 4Z) \leftarrow (0, 0, 0, 0, 2Z, 0) \leftarrow (0, 0, 0, Z, 0, 0)$, то есть нам сейчас достаточно показать как придти из $(0, 0, 0, X, 0, 0)$ в $(0, 0, 0, Z, 0, 0)$, но если мы докажем, что $X \geq Z$, то легким примением операций второго типа можем уменьшать значение $X$ на один и, в итоге, придти в нужную ситуацию. Осталось показать, что $X \geq Z$. Заметим, что $2010 < 2^{2^{2^2}} = x_4$, тогда $Z < Y < x_4^{x_4^{x_4}} = x_{12} < x_{35} = X$, что и требовалось доказать.