Problem 400 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 400 へ行く。
  • 1 (2012-10-28 (日) 00:28:37)

Problem 400 「フィボナッチ木ゲーム」 †

フィボナッチ木とは以下のように再帰的に定義された二分木のことである:

• T(0) はノード(節点)を持たない木(空木)である.
• T(1) はノードを一つだけ持つ二分木である.
• T(k) は T(k-1) と T(k-2) を子ノードとして持つルートノード(最上位にあるノード)からなる.

このような木構造上で二人の対局者がゲームをする. それぞれの局面で対局者はあるノードを選択し, そのノードをルートとする部分木全体を削除する.
木全体のルートノードを強制的に取らされた対局者が敗者となる.

k=1 から k=6 までの T(k) に対し最初の局面で先手必勝となる手は以下のようになる. (訳注:赤いノードで示されている)

#ref(): File not found: "p400_winning.png" at page "Problem 400"

T(k) の木構造上でゲームをした時, 最初の局面で先手必勝となる(すなわち, 後手が勝てる戦略がない)手の数を f(k) としよう.

例として f(5) = 1, f(10) = 17 となる.

f(10000) を求めよ. 末尾18桁を回答として答えよ.