swk's log

* 陣取りゲーム・クイズ [misc]

• http://www.hyuki.com/d/200610.html#i20061009222222

将棋盤(9×9のマス目を持つ盤)を使って二人が陣取りゲームをする。自分の番になったとき、空いているマス目（自分の陣地でも相手の陣地でもないマス目）の中からいくつか選んで「自分の陣地」にすることができる。一度に自分の陣地にできるのは、「1個」か「隣り合った2個」のいずれかである。隣り合った2個は縦の2個でも横の2個でもよい。パスはできない。自分の番になったとき空いているマス目がひとつもなかったら負け。

(追記: 解答編 が公開されたので，ネタバレ反転処理を解除します)

えーと，

先手の立場で，以下のような戦略を考える．

(1) まず最初に，先手は真中の 1 マスを陣地として取る．

(2) この時点で空いているマス目がなすパターン (以下，空きマス配置) は中心対称であり，かつ空いているどのマスから見ても，自分と対称の位置にあるマスは自分自身ではない．さて，このとき後手は，どのような陣地の取り方をしても，空きマス配置の中心対称性を保つことができない．1個を陣地に取るときに保てないのは明らか．2個を陣地に取るときも「隣り合った縦または横の2マス」は「中心対称な2マス」ではあり得ないので，やはり中心対称性は保てない．

(3) 後手が自分の陣地を取った後，先手は，たったいま後手が取ったマスに対して中心対称な位置にあるマスを陣地に取ることができる (必ず空いている)．これにより，空きマス配置は再び中心対称に戻る．

以下，(2)と(3)を繰り返していくことができる．さて，このゲームでは自分の番が終わったあと，空いているマス目が無くなれば勝ちである．一方 (2)において，後手は中心対称性を保った陣地の取り方はできないのだから，空いているマスがひとつもなくなるという中心対称な配置に持ち込むことはできないことになる．よって先手必勝である．

9×9 の盤だけではなく m×n の盤の場合に一般化すると，

m と n がともに奇数の場合は，上記の議論がそのままできるので先手必勝である．

m と n がともに偶数の場合は，初期盤面で既に (2) の状態になってしまっている．よって上記の(2)と(3)で先手と後手を逆にすれば全く同じ議論ができる．よって後手必勝．

m と n の一方が奇数，他方が偶数の場合，先手は最初に真ん中の2マスを陣地に取ることで，中心対称を保つことができる．次の後手の番では，中心対称を保つ陣地の取り方はできない．よって先手必勝．

トーラスの場合への一般化は，この方針では難しいのかな．あまり筋のいい方針ではなかったのかも…

(追記: わりと真っ当な方針だったようで．ていうか 中学入試レベルなんだとか．あわわ)