Математикадан 51-ші халықаралық олимпиада, 2010 жыл, Астана

Бастапқыда ${{B}_{1}}$, ${{B}_{2}}$, ${{B}_{3}}$, ${{B}_{4}}$, ${{B}_{5}}$, ${{B}_{6}}$ алты жәшіктің әрқайсысының ішінде тура бір тиыннан бар. Келесі екі типті операцияларды жүзеге асыруға рұқсат:
1-ші тип: $1\le j\le 5$ үшін кез келген бос емес ${{B}_{j}}$ жәшігін таңдап, оның ішінен бір тиынды алып тастауға және сонымен қатар ${{B}_{j+1}}$ жәшігіне екі тиын салуға болады.
2-ші тип: $1\le k\le 4$ үшін кез келген бос емес ${{B}_{k}}$ жәшігін таңдап, оның ішінен бір тиынды алып тастауға және сонымен қатар ${{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$, что и требовалось доказать.