Problem 459 「どんでん返しゲーム」

どんでん返しゲームとは N x N マスの盤面でプレイする二人用のゲームである.
それぞれのマスには片面が白,もう片面が黒のコマが置かれている.
ゲームはすべてのコマの白い面が見える状態からスタートする.

対局では, 以下の性質を持つ長方形の中のすべてのコマを裏返す:

  • 長方形の一番右上のマスは白のコマ
  • 長方形の幅は完全平方数 (1, 4, 9, 16, ...)
  • 長方形の高さは三角数 (1, 3, 6, 10, ...)
p459-flipping-game-0.png

対局者は交互に上記の作業を行う. すべてのマスを黒に変えたものが勝者となる.

すべてが白いコマの状態になっている N x N の盤面で, 完璧な対局を行うと仮定した時, 先手必勝となる手 (相手がどんな手を差しても勝つことができる最初の手) の数を W(N) としよう.
W(1) = 1, W(2) = 0, W(5) = 8, そして W(102) = 31395.

N=5 の場合, 8つの先手必勝の手がある:

p459-flipping-game-1.png


p459-flipping-game-2.png

W(106) を求めよ.


添付ファイル: filep459-flipping-game-2.png 160件 [詳細] filep459-flipping-game-1.png 156件 [詳細] filep459-flipping-game-0.png 171件 [詳細]

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