IMO 2010 P5

Published on

Statement

Each of the six boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$ initially contains one coin. The following operations are allowed

Type 1) Choose a non-empty box $B_j$, $1 \leq j \leq 5$ remove one coin from $B_j$ and add two coins to $B_{j + 1}$;

Type 2) Choose a non-empty box $B_k$, $1 \leq k \leq 4$, remove one coin from $B_k$ and swap the contents (maybe empty) of the boxes $B_{k + 1}$ and $B_{k + 2}$.

Determine if there exists a finite sequence of operations of the allowed types, such that the five boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$ become empty, while box $B_6$ contains exactly $2010^{2010^{2010}}$ coins.

Tutorial

Lemma 1

It is sufficient to prove we can obtain $\left(0, 0, 0, T, 0, 0\right)$, where $T \geq 2010^{2010^{2010}} / 4$.


Proof.

Now we are at $\left(0, 0, 0, T, 0, 0\right)$, and our goal is to reach $\left(0, 0, 0, 0, 0, 2010^{2010^{2010}}\right)$.

We can do operation 2 repeatedly, until we reach $\left(0, 0, 0, 2010^{2010^{2010}} / 4, 0, 0\right)$.

Then repeatedly apply operation 1 until all coins have been moved to $B_6$. $\square$

Lemma 2

For any three consecutive boxes $\left(n, 0, 0\right)$, we can reach $\left(0, 2^n, 0\right)$.


Proof.

$$ \begin{aligned} &\left(n, 0, 0\right) \\ &\left(n - 1, 2, 0\right) \to \left(n - 1, 0, 4\right) \\ &\left(n - 2, 4, 0\right) \to \left(n - 2, 0, 8\right) \\ &\qquad\vdots \\ &\left(0, 2^n, 0\right) \end{aligned} $$

$\square$

Lemma 3

For any four consecutive boxes $\left(n, 0, 0, 0\right)$, we can reach $\left(0, 2 \uparrow\uparrow n, 0\right)$, where $\uparrow\uparrow$ is Knuth's up-arrow notation.


Proof.

$$ \begin{aligned} &\left(n, 0, 0, 0\right) \\ &\left(n - 1, 2, 0, 0\right) \to \left(n - 1, 0, 2^2, 0\right) \\ &\left(n - 2, 2^2, 0, 0\right) \to \left(n - 2, 0, 2^{2^2}\right) \\ &\left(n - 3, 2^{2^2}, 0, 0\right) \to \left(n - 3, 0, 2^{2^{2^2}}, 0\right) \\ &\qquad\quad\vdots \\ &\left(0, 2 \uparrow\uparrow n, 0, 0\right) \end{aligned} $$

$\square$


$$ \begin{aligned} &\left(1, 1, 1, 1, 1, 1\right) \to \\ &\left(0, 2, 2, 2, 2, 3\right) \to \\ &\left(0, 2, 2, 0, 0, 15\right) \to \\ &\left(0, 2, 1, 2, 0, 15\right) \to \\ &\left(0, 2, 1, 1, 15, 0\right) \to \\ &\left(0, 2, 1, 0, 17, 0\right) \to \\ &\left(0, 2, 0, 17, 0, 0\right) \to \\ &\left(0, 1, 17, 0, 0, 0\right) \to \\ &\left(0, 0, 19, 0, 0, 0\right) \to \\ &\left(0, 0, 0, 2 \uparrow\uparrow 19, 0, 0\right) \end{aligned} $$

with

$$2 \uparrow\uparrow 19 > 2010^{2010^{2010}} / 4$$


No comments

Post a comment