Problem 306 「紙テープゲーム」

次のゲームは, 組み合わせゲーム理論の古典的な例である:

2人のプレイヤーが, 一列に並んだ n 個の白い正方形から開始して, 交互にターンを行う.
各ターンでは, プレイヤーは2つの隣り合う白い正方形を選び, 黒で塗る.
最初に色を塗ることができなくなったプレイヤーが負けとなる.

  • n = 1 の場合, 有効な手はないため, 先手が自動的に負けとなる.
  • n = 2 の場合, 有効な手は1つのみであり, その後, 後手が負けとなる.
  • n = 3 の場合, 有効な手は2つあるが, どちらも後手が負ける状況となる.
  • n = 4 の場合, 有効な手は先手に3つある; 先手は中央の2つの正方形を塗ると勝利できる.
  • n = 5 の場合, 有効な手は先手に4つある(下図に赤で示す); しかしいずれを選んでも, 後手(青)が勝利する.
p_306_pstrip.gif

したがって, 1≦n≦5 に対し, 先手必勝となる n の値は 3 個ある.
同様に, 1≦n≦50 に対し, 先手必勝となる n の値は 40 個ある.

1≦n≦1 000 000 に対し, 先手必勝となる n の値は何個あるか.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-10-17 (日) 21:20:02 (2386d)