第5問

6個の箱

B_1,B_2,B_3,B_4,B_5,B_6

には最初それぞれ1枚のコインが入っている。種類1の操作では、

1\le j\le5

を満たす空でない箱

B_j

を選び、コインを1枚取り出して

B_{j+1}

に2枚加える。種類2の操作では、

1\le k\le4

を満たす空でない箱

B_k

を選び、コインを1枚取り出し、（空でもよい）箱

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)}

を意味する。

ステップ 2/5: 複合操作で指数が生じる

前のステップ次のステップ

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

詳しい解説

状態 $(k,n,0,0)$ の最後の3箱を考える。この3箱の最初の箱で種類1を行い、次の箱で種類1を行って空にする操作を繰り返すと、各巡回は最初の箱のコインを1枚消費し、3番目の箱の枚数を2倍にする。したがって $(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)$ となる。次にこの3箱の最初の箱で種類2を行うと $(0,2^n,0)$ になり、直前の箱で種類2を行えば $(k-1,2^n,0,0)$ を得る。取り出す箱は常に空でないので、すべて合法である。