Problem 5

Each of the six boxes

B_1,B_2,B_3,B_4,B_5,B_6

initially contains one coin. A type 1 operation chooses a nonempty box

B_j

with

1\le j\le5

, removes one coin from it, and adds two coins to

B_{j+1}

. A type 2 operation chooses a nonempty box

B_k

with

1\le k\le4

, removes one coin from it, and exchanges the contents of (possibly empty) boxes

B_{k+1}

and

B_{k+2}

. Determine whether a finite sequence of operations can leave

B_1,B_2,B_3,B_4,B_5

empty and

B_6

containing exactly

2010^{2010^{2010}}

coins. Here

a^{b^c}

means

a^{(b^c)}

Step 2 of 5: A compound move creates an exponential

Previous step Next step

(k,n,0,0)\to(k-1,2^n,0,0)\qquad(k\ge1,n>0)

Detailed analysis

Consider the last three boxes in the state $(k,n,0,0)$ . Repeatedly apply type 1 at the first of these three boxes and use type 1 on the next box to clear it; each cycle consumes one coin from the first box and doubles the number in the third. This gives $(n,0,0)\to(n-1,2,0)\to(n-1,0,4)\to(n-2,4,0)\to(n-2,0,8)\to\cdots\to(1,0,2^n)$ . A type 2 at the first of these three boxes then gives $(0,2^n,0)$ , and a type 2 at the preceding box gives $(k-1,2^n,0,0)$ . Every operation is legal because the box named for removal is nonempty.