Problem 334

Problem 334 「豆くずし」 †

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

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

次の数列が与えられる：

• t0 = 123456.
• 
  • xは床関数を表し,
  • はビットの XOR 演算である.
• bi = ( ti mod 211 ) + 1.

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

1500 枚の隣り合うボウルにそれぞれ b1, b2,..., b1500 個の豆がある状態を考えよう. 他のボウルはすべて空である. ゲームを終えるのにかかる手の数を求めよ.