334 : 豆くずし

プラトンの天国には, 直線状に無限の枚数のボウルが存在する. 各ボウルは０個以上の有限個の豆が含まれている. 子供がゲームをプレイする. このゲームでは, １種類の手だけが許される：どれかのボウルから豆を２個取り除き, 両隣の２個のボウルに１個ずつ入れる. どのボウルも１個ないしは０個の豆を含んでいれば, ゲームは終了する.

例えば, それぞれ２個と３個の豆を含んだ隣り合う２枚のボウルを考えよう. 他のボウルはすべて空である. 次の８手でゲームは終了する：

p334_beans.gif

次の数列が与えられる：

• $t_0 = 123456$

• $\displaystyle t_i = \left \{ \begin{array}{ll}\displaystyle \frac{t_{i-1}}{2} & t_{i-1}が偶数のとき\\ \\ \displaystyle \Big \lfloor \frac{t_{i-1}}{2} \Big \rfloor \oplus 926252 & t_{i-1}が奇数のとき \end{array} \right .$

  • $\lfloor \cdot \rfloor$は床関数を表す

  • $\oplus$はビットごとのXOR演算を表す

• $b_i = ( t_i \mod 2^{11} ) + 1$

最後の数列の最初の２項は$b_1 = 289, b_2 = 145$である. ２枚の隣り合うボウルに$b_1$個と$b_2$個の豆がある状態から始めると, ゲームを終えるのに 3419100 手が必要である.

1500枚の隣り合うボウルにそれぞれ$b_1, b_2,\dots, b_{1500}$個の豆がある状態を考えよう. 他のボウルはすべて空である. ゲームを終えるのにかかる手の数を求めよ.