Problem 331 「十字返し」

N×N の円盤が正方形のゲーム盤に置かれている. 円盤にはそれぞれ黒面と白面がある.

各手番では, 円盤を1枚選び, 同じ横列と同じ縦列にある円盤をすべて裏返す:ゆえに 2×N-1 枚の円盤が裏返される. すべての円盤が白面となればゲームは終了する.
次の例は 5×5 の盤でのゲームを示している.

p_331_crossflips3.gif

このゲームを終わらせる最小の手数は 3 であることが示せる.

N×N の盤の左下の円盤を座標 (0,0) とする.
右下の円盤は座標 (N-1,0) で左上の円盤は座標 (0,N-1) である.

N×N 枚の盤での次の配置を CN とする:
p_331_crossflips1.gifを満たす (x,y) の円盤は黒面である;さもなくば白面である. C5 は上に示されている.

配置 CN から始めてゲームを終わらせる最小の手数を T(N) とする. 配置 CN が解けない場合は T(N) は 0 である.
T(5)=3 であることが分かる. また T(10)=29, T(1 000)=395253 である.

p_331_crossflips2.gif を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-04-06 (水) 22:34:48 (2214d)