51st IMO Shortlisted Problems

Denote by $\left(a_1,a_2,\dots ,a_n\right)\to \left(a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }\right)$ the following: if some consecutive stacks contain $a_1,\dots ,a_n$ coins, then it is possible to perform several allowed moves such that the stacks contain $a_1^{\prime },\dots ,a_n^{\prime }$ coins respectively, whereas the contents of the other stacks remain unchanged.

Let $A=2010^{2010}$ or $A=2010^{2010^{2010}}$, respectively. Our goal is to show that $$(1,1,1,1,1,1)\to (0,0,0,0,0,A)$$ First we prove two auxiliary observations.

Lemma 1. $(a,0,0)\to \left(0,2^a,0\right)$ for every $a\ge 1$.

Proof. We prove by induction that $(a,0,0)\to \left(a-k,2^k,0\right)$ for every $1\le k\le a$. For $k=1$, apply Move 1 to the first stack: $$(a,0,0)\to (a-1,2,0)=\left(a-1,2^1,0\right)$$ Now assume that $k<a$ and the statement holds for some $k<a$. Starting from $\left(a-k,2^k,0\right)$, apply Move 1 to the middle stack $2^k$ times, until it becomes empty. Then apply Move 2 to the first stack: $$\left(a-k,2^k,0\right)\to \left(a-k,2^k-1,2\right)\to \cdots \to \left(a-k,0,2^{k+1}\right)\to \left(a-k-1,2^{k+1},0\right)$$ Hence, $$(a,0,0)\to \left(a-k,2^k,0\right)\to \left(a-k-1,2^{k+1},0\right)$$

Lemma 2. For every positive integer $n$, let $P_n=\underset{n}{\underbrace{2^{2^{.2}}}}$ (e.g. $P_3=2^{2^2}=16$ ). Then $(a,0,0,0)\to \left(0,P_a,0,0\right)$ for every $a\ge 1$.

Proof. Similarly to Lemma 1, we prove that $(a,0,0,0)\to \left(a-k,P_k,0,0\right)$ for every $1\le k\le a$. For $k=1$, apply Move 1 to the first stack: $$(a,0,0,0)\to (a-1,2,0,0)=\left(a-1,P_1,0,0\right)$$ Now assume that the lemma holds for some $k<a$. Starting from ( $a-k,P_k,0,0$ ), apply Lemma 1, then apply Move 1 to the first stack: $$\left(a-k,P_k,0,0\right)\to \left(a-k,0,2^{P_k},0\right)=\left(a-k,0,P_{k+1},0\right)\to \left(a-k-1,P_{k+1},0,0\right)$$ Therefore, $$(a,0,0,0)\to \left(a-k,P_k,0,0\right)\to \left(a-k-1,P_{k+1},0,0\right)$$

Now we prove the statement of the problem.

First apply Move 1 to stack 5, then apply Move 2 to stacks $S_4,S_3,S_2$ and $S_1$ in this order. Then apply Lemma 2 twice: $$\begin{array}{c}(1,1,1,1,1,1)\to (1,1,1,1,0,3)\to (1,1,1,0,3,0)\to (1,1,0,3,0,0)\to (1,0,3,0,0,0)\to \\ \to (0,3,0,0,0,0)\to \left(0,0,P_3,0,0,0\right)=(0,0,16,0,0,0)\to \left(0,0,0,P_{16},0,0\right)\end{array}$$ We already have more than $A$ coins in stack $S_4$, since $$A\le 2010^{2010^{2010}}<{\left(2^{11}\right)}^{2010^{2010}}=2^{11\cdot 2010^{2010}}<2^{2010^{2011}}<2^{{\left(2^{11}\right)}^{2011}}=2^{2^{11\cdot 2011}}<2^{2^{2^{15}}}<P_{16}.$$ To decrease the number of coins in stack $S_4$, apply Move 2 to this stack repeatedly until its size decreases to $A/4$. (In every step, we remove a coin from $S_4$ and exchange the empty stacks $S_5$ and $S_6$.) $$\begin{array}{rl}\left(0,0,0,P_{16},0,0\right)\to & \left(0,0,0,P_{16}-1,0,0\right)\to \left(0,0,0,P_{16}-2,0,0\right)\to \\ & \to \cdots \to (0,0,0,A/4,0,0)\end{array}$$ Finally, apply Move 1 repeatedly to empty stacks $S_4$ and $S_5$ : $$(0,0,0,A/4,0,0)\to \cdots \to (0,0,0,0,A/2,0)\to \cdots \to (0,0,0,0,0,A)$$