2010 IMO Problems/Problem 5

Problem

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.

Author: Hans Zantema

Solution

Let the notation $[a_1,a_2,a_3,a_4,a_5,a_6]$ be the configuration in which the $x$-th box has $a_x$ coin,

Let $T=2010^{2010^{2010}}$.


Our starting configuration is $[1,1,1,1,1,1]$


We need these compound moves:

Compound move 1: $[a,0]\rightarrow[0,2a]$, this is just repeated type 1 move on all $a$ coins.

Compound move 2: $[a,0,0]\rightarrow[0,2^a,0]$, apply type 1 move on 1 of the coin to get $[a-1,2,0]$, then apply compound move 1 to the 2 coins to get $[a-1,0,2^2]$, apply type 2 move and get $[a-2,2^2,0]$, and repeat compound move 1 and type 2 move until $[0,2^a,0]$ is achieve.

Compound move 3: $[a,b,0,0]\rightarrow[a-1,2^b,0,0]$, apply compound move 2 to obtain $[a,0,2^b,0]$ and use type 2 move to get $[a-1,2^b,0,0]$

Compound move 4: $[a,0,0,0]\rightarrow[0,2^{2^{.^{.^{.^2}}}},0,0]$ with $a$ $2$'s. Apply compound move 3 $a$ times.

Compound move 5: $[a,0,0]\rightarrow[b,0,0]$ with $a>b$, use type 2 move $(a-b)$ times.

Let's follow this move:

$[1,1,1,1,1,1] \rightarrow[0,3,1,1,1,1] \rightarrow[0,2,3,1,1,1]\rightarrow[0,2,1,5,1,1]\rightarrow[0,2,1,1,9,1]\rightarrow[0,2,1,1,0,19]\rightarrow[0,1,19,0,0,0]$


Using Compound move 1, 4 and 5, We can obtain:

$[0,1,19,0,0,0]\rightarrow[0,1,0,X,0,0]\rightarrow[0,0,X,0,0,0]\rightarrow[0,0,0,Y,0,0]\rightarrow[0,0,0,T/4,0,0]\rightarrow[0,0,0,0,T/2,0]\rightarrow[0,0,0,0,0,T]$

, where $X, Y = 2^{2^{.^{.^{.^2}}}}$ where X has $19$ 2's and Y has $X$ 2's, and $Y$ is clearly bigger then $T/4$


See Also

2010 IMO (Problems) • Resources
Preceded by
Problem 4
1 2 3 4 5 6 Followed by
Problem 6
All IMO Problems and Solutions