フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

勝敗が周期34で変化するゲーム

先日、いつものように夜眠れずに布団の中で数学のことを考えていたところ、ふと面白いゲームを思いつきました。

ルールは簡単です。1\times nのマス目に2人で交互に1\times 2のタイルを置いていきます。タイルは重なってはいけません。先に置けなくなったプレイヤーが負けです。

f:id:fibonacci_freak:20170902015458p:plain

布団の中でしばらく考えたところ、まずn2以上の偶数の時は先手必勝であることがわかりました。必勝手順は次の通りです。

(1) 先手は最初に中央の2マスにタイルを置く。

(2) その後は後手が置いたタイルと左右対称な位置に置くことを繰り返す。

こうすれば先手が置いた後は常に盤面が左右対称になるため、先手が置けなくなることは決してありません。

次にnが奇数の時を順番に考えていくと次のことがわかりました。

n=3は先手必勝。

n=5は後手必勝。

n=7は先手必勝。

n=9は後手必勝。

n=11は先手必勝。

n=13は先手必勝。

これらは単純に全ての手のパターンを考えることで得られます。

ここまでは特に規則性が無いように見えたので、何か手がかりになる情報がないかと思いネットで調べてみました。すると次のような記述が見つかりました(要約)。

このゲームはDawson's Kaylesと呼ばれ、octal gameという種類に属する。octal gameにはGuy-Smith periodicityという定理が知られており、それによればDawson's Kaylesの勝者はnについて有限個の例外を除き周期34で繰り返す。具体的には後手必勝となるのはn=0,1,15,35またはn\equiv 5,9,21,25,29~\mathrm{mod}~34の時に限る。

 

さすがにこれには驚きました。周期34で繰り返すなんて誰が予想できるでしょうか!

そういうわけで今回はこの周期性(Guy-Smith periodicity)をDawson's Kaylesの場合に限って証明したいと思います。

 

Grundy値について

今回の証明の鍵となるのが、ゲームの局面について定まるGrundy値と言う概念です。

ここでは「有限の手数で勝敗が決することが保証され、確率的要因が絡まず、両者の打てる手が対等で、盤面の情報が全て共有されており、打てる手が無くなった人が負ける」というタイプのゲームのみを考えることにします。Dawson's Kaylesはこのようなゲームの一例です。あとで見ますが、この種のゲームの局面についての命題を示す時は「ゲームが終わるまでの最長手数」に関する帰納法を使うことができる、ということに注意しましょう。

ゲームの局面Gについて、局面G'Gから一手で得られることをG'\in Gと表記します。

定義. ゲームの局面Gに対し、そのGrundyg(G)を以下のように帰納的に定める。
\displaystyle g(G)=\mathop{\mathrm{mex}}_{G'\in G}g(G')
ただし\mathop{\mathrm{mex}}_{x\in S}xSに現れない最小の非負整数(Sが空なら0)を指す。

このとき局面Gが後手必勝であることはg(G)=0と同値です。なぜなら(上に述べた帰納法で)Gが先手必勝となるのはG'\in Gで後手必勝のものが存在することと同値で、これは帰納法の仮定からg(G')=0なるG'が存在すること、すなわちその\mathop{\mathrm{mex}}0にならないことと同値だからです。

Grundy値はただの数字の割り当てではなく、際立った性質を持っています。それは「局面の直和」に対してうまく振る舞うということです。2つの局面G_1,G_2の直和G_1+G_2とは「2つの局面を並べた*1ゲームの局面」のことです。例えば1\times nのDawson's Kaylesの初期局面をK_nとすると、K_{10}の中央にタイルを置いた局面はK_4+K_4と書くことができます。

定理(Sprague-Grundy). ゲームの局面G_1,G_2についてg(G_1+G_2)=g(G_1)\oplus g(G_2). ただしA\oplus BA,Bの2進表記の排他的論理和である。

証明. 帰納法で示す。G'\in (G_1+G_2)G'_1+G_2~(G'_1\in G_1)またはG_1+G'_2~(G'_2\in G_2)と書くことができる。よって帰納法の仮定より

S=\{g(G'_1)\oplus g(G_2)\mid G'_1\in G_1\}\cup\{g(G_1)\oplus g(G'_2)\mid G'_2\in G_2\}

と定めた時

\displaystyle g(G_1+G_2)=\mathop{\mathrm{mex}}_{x\in S}x.

g(G_1)\oplus g(G_2)\not\in Sに注意すれば、示すべきことはx\lt g(G_1)\oplus g(G_2)\Rightarrow x\in Sと言い換えることができる。以下これを示す。

g(G_1)\oplus g(G_2)\oplus xの2進表記の桁数をmとする。自然数aの2進表記の下からm桁目を[a]_mと書くことにすると

[g(G_1)\oplus g(G_2)\oplus x]_m=1.

x\lt g(G_1)\oplus g(G_2)なので[x]_m=0, [g(G_1)]_m=0, [g(G_2)]_m=1としてよい。するとg(G_1)\oplus x \lt g(G_2)なので、g(G_2)の定義を考えればあるG'_2\in G_2があってg(G'_2)=g(G_1)\oplus xとなる。移項してx=g(G_1)\oplus g(G'_2)なのでx\in Sがわかった。~~~\square

 

周期性の証明

さて、Dawson's Kaylesに話を戻しましょう。H_n:=g(K_n)と書くことにします。定義よりH_0=0です。

これから示すGuy-Smith periodicityというのは大雑把に言うと「Grundy値がある範囲で周期的になっていればそこから先ずっと周期的になる」という定理です。これにより、数の小さい範囲で具体的に勝敗を計算して周期34の部分を見つけるだけで、その先の周期性まで示すことができるというわけです。

定理. 正整数i,pが存在してH_{n+p}=H_ni\leq n\lt 2i+p+2に対して成り立つならば、任意のn\gt iに対しても成り立つ。

 証明. n\geq 2i+p+2についてH_{n+p}=H_nであることを帰納法により示す。K_nから一手だけ打った後の局面は、a+b+2=nを満たすある非負整数a,bに対する直和K_a+K_bである。よってGrundy値の定義とSprague-Grundyの定理より

\displaystyle H_{n+p}=\mathop{\mathrm{mex}}_{a+b=n+p-2}H_a\oplus H_b.

ここでa+b=n+p-2\geq 2(i+p)よりa,bの少なくとも片方はi+p以上なので、b\geq i+pとしてよい。すると帰納法の仮定よりH_b=H_{b-p}なので、c=b-pとおけば

\displaystyle H_{n+p}=\mathop{\mathrm{mex}} _{a+c=n-2,~c\geq i}H_a\oplus H_c.

n-2\geq 2iより、a+c=n-2という分解においてc\geq iと仮定しても一般性を失っていない。よって上式は

\displaystyle \mathop{\mathrm{mex}} _{a+c=n-2}H_a\oplus H_c=H_n

に等しい。~~~\square

 

具体的な計算

それではDawson's KaylesのGrundy値が本当に周期34を持つのか確かめてみましょう。愚直に計算すると(コンピュータに計算させると)以下の結果が得られます。字が細いので別タブなどで拡大して見てください。

f:id:fibonacci_freak:20170904011542p:plain

H_{n+34}\neq H_nであるものは桃色で示されています。青で示したi=53\leq n\lt 2i+34+2=142の部分はH_{n+34}=H_nを満たしています。ゆえに先ほど示した定理により、この後もずっと周期34で繰り返すことがわかりました!

 

感想

ところで上の表を見ていると、私にはこの周期性が「数列の途中で偶然生じたものがGuy-Smith periodicityによって繰り返されてしまった」というものには思えず、最初から何か別の理由で周期性が生じているのではないか、という感覚が拭きれません(数学的ではありませんが)。青で塗られた周期的な列は、偶然できたにしては長すぎるように感じます。

今のところGrundy値の周期の長さを計算する方法は、上のように愚直に計算していって周期らしきものを見つける以外ありません。しかし私はいつか必ず34という数の本当の理由が明かされる日が来ると信じています。

*1:一度にどちらか一方だけに打てる。