Problem 334 「豆くずし」

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

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

p_334_beans.gif

次の数列が与えられる:

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

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

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


添付ファイル: file1.gif 371件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-06-16 (木) 10:07:09 (2167d)