石取りゲームにおける『グランディ数』及び、そこに潜む『未解決問題』を、中学・高校生にも分かるように解説！
『石取りゲーム』というのがあります。なおこのゲームは、ニコニコ生放送 『MATH POWER 2022』という番組内で紹介されたゲームで、このゲームに潜む未解決問題に、二日かけて徹夜で挑むぶっ通し企画で登場します。
なおこの記事は、MATH POWER の HP
にある説明文を参照しています。それではこのゲームの解説です。
１．『石取りゲーム』について
ある一定数の石が目の前にあります。
石の数は、ゲームが成立するだけの数を自由に選ぶことができます。２人で交互にその石を取っていくのですが、取り方のルールとして
①１個取る、②２個取る、③３個取る
の３通りの石の取り方があります。その都度いずれかの方法を自由に選んで交互に石を取っていき、最後に石を取った方が勝ち、となるゲームです。
例えば、目の前に１３個の石があったとします。相手が先手だとすると
最初 ①➁➂④⑤⑥➆⑧⑨⑩⑪⑫⑬
相手 ３個取る $${\rightarrow}$$ 残りの石は１０個
①②➂④⑤⑥➆⑧⑨⑩
自分 ２個とる $${\rightarrow}$$ 残りの石は８個
①②➂④⑤⑥➆⑧
相手 １個取る $${\rightarrow}$$ 残りの石は７個
①②➂④⑤⑥➆
自分 ３個取る $${\rightarrow}$$ 残りの石は４個
①②➂④
相手 ２個取る $${\rightarrow}$$ 残りの石は２個
①②
自分 ２個取る $${\rightarrow}$$ 残りの石は０個
となれば、最後に石を取った自分の勝ちとなります。
このゲームには必勝法がありまして、「残りの石の個数が４の倍数」となるように石を取っていけば必ず勝ちになります。例えば、先ほどの例で言うと
最初 ①➁➂④⑤⑥➆⑧⑨⑩⑪⑫⑬
相手 ３個取る $${\rightarrow}$$ 残りの石は１０個
①②➂④⑤⑥➆⑧⑨⑩
自分 ２個とる $${\rightarrow}$$ 残りの石は８個（４の倍数）
①②➂④⑤⑥➆⑧
相手 １個取る $${\rightarrow}$$ 残りの石は７個
①②➂④⑤⑥➆
自分 ３個取る $${\rightarrow}$$ 残りの石は４個（４の倍数）
①②➂④
相手 ２個取る $${\rightarrow}$$ 残りの石は２個
①②
自分 ２個取る $${\rightarrow}$$ 残りの石は０個
と、残りの石の個数が４の倍数になるように石を取っていく、逆に言えば、石の個数が４の倍数になる局面を常に相手に提示していくわけです。
なお、自分の手番で石の個数が４の倍数になったときは、相手の手番で４の倍数になるよう途中で調整していきます。例えば次のような場合です。
最初 ①➁➂④⑤⑥➆⑧⑨⑩⑪⑫⑬
相手 １個取る $${\rightarrow}$$ 残りの石は１２個
①➁➂④⑤⑥➆⑧⑨⑩⑪⑫
$${\rightarrow}$$ 自分に４の倍数を提示されても
自分 １個とる $${\rightarrow}$$ 残りの石は１１個
①➁➂④⑤⑥➆⑧⑨⑩⑪
相手 ２個取る $${\rightarrow}$$ 残りの石は９個
①➁➂④⑤⑥➆⑧⑨
自分 １個取る $${\rightarrow}$$ 残りの石は８個（４の倍数）
①➁➂④⑤⑥➆⑧
$${\rightarrow}$$ ４の倍数が発生、後はこれをキープ
相手 ３個取る $${\rightarrow}$$ 残りの石は５個
①➁➂④⑤
自分 １個取る $${\rightarrow}$$ 残りの石は４個（４の倍数）
①➁➂④
相手 ２個取る $${\rightarrow}$$ 残りの石は２個
①➁
自分 ２個取る $${\rightarrow}$$ 残りの石は０個
となれば、やはり最後に石を取った自分の勝ちとなります。結局、残りの石の個数が「４個」の局面を相手に提示できれば
相手が１個取ると、自分は残りの３個すべてを取って自分の勝ち
相手が２個取ると、自分は残りの２個すべてを取って自分の勝ち
相手が３個取ると、自分は残りの１個すべてを取って自分の勝ち
と、自分に勝ちが必ず訪れる仕組みです。残りの石の個数が４の倍数となる局面を、最後までキープし続けていけばよいわけです。
２．石取りゲームを拡張する
さて、このゲームを拡張します。取れる石の数を変化させます。先の例では
①１個取る、②２個取る、③３個取る
でしたが、このときは「残りの石の個数が４の倍数」になるように石をとれば勝ちでした。これを例えば
①２個取る、②３個取る
または
①２個取る、②４個取る、③７個取る
というふうに、取り方のルールを自由に変えていった場合、勝ちパターンはどのように変化するでしょうか。ちなみに
①２個取る、②３個取る
のルールだと「５の倍数をキープしていけば勝ち」となります。例えば、仮に石の数が１９個、相手が先手だとすると
最初 ①➁➂④⑤⑥➆⑧⑨⑩⑪⑫⑬⑭⑮⑯⑰⑱⑲
相手 ３個取る $${\rightarrow}$$ 残りの石は１６個
①➁➂④⑤⑥➆⑧⑨⑩⑪⑫⑬⑭⑮⑯
自分 ２個とる $${\rightarrow}$$ 残りの石は１４個
①➁➂④⑤⑥➆⑧⑨⑩⑪⑫⑬⑭
相手 １個取る $${\rightarrow}$$ 残りの石は１３個
①➁➂④⑤⑥➆⑧⑨⑩⑪⑫⑬
自分 ３個取る $${\rightarrow}$$ 残りの石は１０個（５の倍数）
①➁➂④⑤⑥➆⑧⑨⑩
$${\rightarrow}$$ ここで５の倍数が発生、後はこれをキープ
相手 ３個取る $${\rightarrow}$$ 残りの石は７個
①➁➂④⑤⑥➆
自分 ２個取る $${\rightarrow}$$ 残りの石は５個（５の倍数）
①➁➂④⑤
相手 ２個取る $${\rightarrow}$$ 残りの石は３個
①➁➂
自分 ３個取る $${\rightarrow}$$ 残りの石は０個
と、最後に石を取った自分の勝ちとなります。①２個取る、②３個取る
のルールだと「５の倍数をキープしていけば勝ち」となるわけです（注１）。
３．『グランディ数』について
ここで、あらゆる石の取り方（ルール）において、どういうときに必勝形になるかについては、次の『グランディ数』というのが役立ちます。
『グランディ数』の定義
１．終了局面のグランディ数は０とする。
２．他の局面は、１手で移行できる局面すべてのグランディ数について、その値すべてを０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ から除いたときの最小の値が、その局面のグランディ数である。
ではこの定義をもとに、具体的にグランディ数を求めてみましょう。手始めに最初に上げたルール、石の取り方が
①１個取る、②２個取る、③３個取る
のときのグランディ数を求めてみます。グランディ数はある石の取り方（ルール）において、残った石の個数の局面それぞれについて決定されます。既知となった前の局面のグランディ数を用いて、今現在の局面のグランディ数が決定されます。具合的に求めてみます。
＜石が０個の局面のグランディ数＞
$${\rightarrow}$$ 終了局面なので定義よりグランディ数は０と決定・・・$${(*0)}$$
＜石が１個の局面のグランディ数＞
このときの一手で移行できる局面は、石を１個取った「石が０個の局面」のみ。 ① $${\rightarrow}$$０個
$${\rightarrow}$$ 石を１個取る
$${\rightarrow}$$ 石が０個の局面
$${\rightarrow}$$ 石が０個の局面のグランディ数は、$${(*0)}$$ より０
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその０を除く
$${\rightarrow}$$ その集合は $${\{\underline{1}, 2, 3, \cdots\}}$$ となる
$${\rightarrow}$$ この集合の要素のうち最小の整数は１（下線部）
$${\rightarrow}$$ よって、石が１個の局面のグランディ数は１と決定・・・$${(*1)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c}
局面の石の数 & 0 & 1\\
\hline
グランディ数 & 0 & 1
\end{array}
$$
となります。
＜石が２個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を１個取った「石が１個の局面」
①➁ $${\rightarrow}$$ ①
(case2) 石を２個取った「石が０個の局面」
①➁ $${\rightarrow}$$０個
の２局面。
(case1)
$${\rightarrow}$$ 石を１個取る
$${\rightarrow}$$ 石が１個の局面
$${\rightarrow}$$ 石が１個の局面のグランディ数は、$${(*1)}$$ より１
(case2)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が０個の局面
$${\rightarrow}$$ 石が０個の局面のグランディ数は、$${(*0)}$$ より０
(case1~2) より
$${\rightarrow}$$ 石が２個の局面から１手で移行できる局面のグランディ数は０と１
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその０と１を除く
$${\rightarrow}$$ その集合は $${\{\underline{2}, 3, 4, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は２（下線部）
$${\rightarrow}$$ よって、石が２個の局面のグランディ数は２と決定・・・$${(*2)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c}
局面の石の数 & 0 & 1 & 2\\
\hline
グランディ数 & 0 & 1 & 2
\end{array}
$$
となります。
＜石が３個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を１個取った「石が２個の局面」
①➁➂ $${\rightarrow}$$ ①➁
(case2) 石を２個取った「石が１個の局面」
①➁➂ $${\rightarrow}$$ ①
(case2) 石を３個取った「石が０個の局面」
①➁➂ $${\rightarrow}$$０個
の３局面。
(case1)
$${\rightarrow}$$ 石を１個取る
$${\rightarrow}$$ 石が２個の局面
$${\rightarrow}$$ 石が２個の局面のグランディ数は、$${(*2)}$$ より２
(case2)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が１個の局面
$${\rightarrow}$$ 石が１個の局面のグランディ数は、$${(*1)}$$ より１
(case3)
$${\rightarrow}$$ 石を３個取る
$${\rightarrow}$$ 石が０個の局面
$${\rightarrow}$$ 石が０個の局面のグランディ数は、$${(*0)}$$ より０
(case1~3) より
$${\rightarrow}$$ 石が３個の局面から１手で移行できる局面のグランディ数は０と１と２
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその０と１と２を除く
$${\rightarrow}$$ その集合は $${\{3, 4, 5, 6, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は３
$${\rightarrow}$$ よって、石が３個の局面のグランディ数は３と決定・・・$${(*3)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3\\
\hline
グランディ数 & 0 & 1 & 2 & 3
\end{array}
$$
となります。
＜石が４個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を１個取った「石が３個の局面」
①➁➂④ $${\rightarrow}$$ ①➁➂
(case2) 石を２個取った「石が２個の局面」
①➁➂④ $${\rightarrow}$$ ①➁
(case3) 石を３個取った「石が１個の局面」
①➁➂④ $${\rightarrow}$$ ①
の３局面。
(case1)
$${\rightarrow}$$ 石を１個取る
$${\rightarrow}$$ 石が３個の局面
$${\rightarrow}$$ 石が３個の局面のグランディ数は、$${(*3)}$$ より３
(case2)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が２個の局面
$${\rightarrow}$$ 石が２個の局面のグランディ数は、$${(*2)}$$ より２
(case3)
$${\rightarrow}$$ 石を３個取る
$${\rightarrow}$$ 石が１個の局面
$${\rightarrow}$$ 石が１個の局面のグランディ数は、$${(*1)}$$ より１
(case1~3) より
$${\rightarrow}$$ 石が４個の局面から１手で移行できる局面のグランディ数は１と２と３
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその１と２と３を除く
$${\rightarrow}$$ その集合は $${\{0, 4, 5, 6, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は０
$${\rightarrow}$$ よって、石が４個の局面のグランディ数は０と決定・・・$${(*4)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4\\
\hline
グランディ数 & 0 & 1 & 2 & 3 & 0
\end{array}
$$
となります。ここでグランディ数が０に戻りました。
＜石が５個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を１個取った「石が４個の局面」
①➁➂④⑤ $${\rightarrow}$$ ①➁➂④
(case2) 石を２個取った「石が３個の局面」
①➁➂④⑤ $${\rightarrow}$$ ①➁➂
(case3) 石を３個取った「石が２個の局面」
①➁➂④⑤ $${\rightarrow}$$ ①➁
の３局面。
(case1)
$${\rightarrow}$$ 石を１個取る
$${\rightarrow}$$ 石が４個の局面
$${\rightarrow}$$ 石が４個の局面のグランディ数は、$${(*4)}$$ より０
(case2)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が３個の局面
$${\rightarrow}$$ 石が３個の局面のグランディ数は、$${(*3)}$$ より３
(case3)
$${\rightarrow}$$ 石を３個取る
$${\rightarrow}$$ 石が２個の局面
$${\rightarrow}$$ 石が２個の局面のグランディ数は、$${(*2)}$$ より２
(case1~3) より
$${\rightarrow}$$ 石が５個の局面から１手で移行できる局面のグランディ数は０と２と３
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその０と２と３を除く
$${\rightarrow}$$ その集合は $${\{1, 4, 5, 6, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は１
$${\rightarrow}$$ よって、石が５個の局面のグランディ数は１と決定・・・$${(*5)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5\\
\hline
グランディ数 & 0 & 1 & 2 & 3 & 0 & 1
\end{array}
$$
となります。最初の「０１」の並びに戻り、なにやら周期性が示唆されます。実際、石の取り方が
①１個取る、②２個取る、③３個取る
のときのグランディ数は、次のように決定されます。
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots\\
\hline
グランディ数 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & \cdots
\end{array}
$$
グランディ数の並びを見ると、４つの数「０１２３」が周期的に現れることが見て取れます。
４．『グランディ数列』について
このグランディ数の値の列
$${\underline{０１２３}０１２３０１２３０１２３ \cdots}$$
を『グランディ数列』といいます。４つの数「$${０１２３}$$」（下線部）が周期的に現れるので、このグランディ数列の『周期は４』となります。
では次に、石の取り方が
①２個取る、②３個取る
のときのグランディ数列を求めてみましょう。周期性が現れるでしょうか？
＜石が０個の局面のグランディ数＞
$${\rightarrow}$$ 終了局面なので定義よりグランディ数は０と決定・・・$${(*0)}$$
＜石が１個の局面のグランディ数＞
$${\rightarrow}$$ 終了局面なので定義よりグランディ数は０と決定・・・$${(*1)}$$
石の取り方は「①２個取る、②３個取る」の２通りしかないので、残った１個の石は取れません。よってこの局面は終了局面となります。
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c}
局面の石の数 & 0 & 1\\
\hline
グランディ数 & 0 & 0
\end{array}
$$
となります。
＜石が２個の局面のグランディ数＞
このときの１手で移行できる局面は、石を２個取った「石が０個の局面」のみ。①➁ $${\rightarrow}$$ ０個
$${\rightarrow}$$ 石が２個取れる
$${\rightarrow}$$ 石が０個の局面
$${\rightarrow}$$ 石が０個の局面のグランディ数は、$${(*0)}$$ より０
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその０を除く
$${\rightarrow}$$ その集合は $${\{1, 2, 3, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の整数は１
$${\rightarrow}$$ よって、石が２個の局面のグランディ数は１と決定・・・$${(*2)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c}
局面の石の数 & 0 & 1 & 2\\
\hline
グランディ数 & 0 & 0 & 1
\end{array}
$$
となります。
＜石が３個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を２個取った「石が１個の局面」
①➁➂ $${\rightarrow}$$ ①
(case2) 石を３個取った「石が０個の局面」
①➁➂ $${\rightarrow}$$ ０個
の２局面。
(case1)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が１個の局面
$${\rightarrow}$$ 石が１個の局面のグランディ数は、$${(*1)}$$ より０
(case2)
$${\rightarrow}$$ 石を３個取る
$${\rightarrow}$$ 石が０個の局面
$${\rightarrow}$$ 石が０個の局面のグランディ数は、$${(*2)}$$ より０
(case1~2) より
$${\rightarrow}$$ 石が３個の局面から１手で移行できる局面のグランディ数は０
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその０を除く
$${\rightarrow}$$ その集合は $${\{1, 2, 3, 4, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は１
$${\rightarrow}$$ よって、石が３個の局面のグランディ数は１と決定・・・$${(*3)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3\\
\hline
グランディ数 & 0 & 0 & 1 & 1
\end{array}
$$
となります。
＜石が４個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を２個取った「石が２個の局面」
①➁➂④ $${\rightarrow}$$ ①➁
(case2) 石を３個取った「石が１個の局面」
①➁➂④ $${\rightarrow}$$ ①
の２局面。
(case1)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が２個の局面
$${\rightarrow}$$ 石が２個の局面のグランディ数は、$${(*2)}$$ より１
(case2)
$${\rightarrow}$$ 石を３個取る
$${\rightarrow}$$ 石が１個の局面
$${\rightarrow}$$ 石が１個の局面のグランディ数は、$${(*1)}$$ より０
(case1~2) より
$${\rightarrow}$$ 石が４個の局面から１手で移行できる局面のグランディ数は０と１
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその０と１を除く
$${\rightarrow}$$ その集合は $${\{2, 3, 4, 5, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は２
$${\rightarrow}$$ よって、石が４個の局面のグランディ数は２と決定・・・$${(*4)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4\\
\hline
グランディ数 & 0 & 0 & 1 & 1 & 2
\end{array}
$$
となります。
＜石が５個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を２個取った「石が３個の局面」
①➁➂④⑤ $${\rightarrow}$$ ①➁➂
(case2) 石を３個取った「石が２個の局面」
①➁➂④⑤ $${\rightarrow}$$ ①➁
の２局面。
(case1)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が３個の局面
$${\rightarrow}$$ 石が３個の局面のグランディ数は、$${(*3)}$$ より１
(case2)
$${\rightarrow}$$ 石が３個取れる
$${\rightarrow}$$ 石が２個の局面
$${\rightarrow}$$ 石が２個の局面のグランディ数は、$${(*2)}$$ より１
(case1~2) より
$${\rightarrow}$$ 石が５個の局面から１手で移行できる局面のグランディ数は１
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその１を除く
$${\rightarrow}$$ その集合は $${\{0, 2, 3, 4, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は０
$${\rightarrow}$$ よって、石が５個の局面のグランディ数は０と決定・・・$${(*5)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5\\
\hline
グランディ数 & 0 & 0 & 1 & 1 & 2 & 0
\end{array}
$$
となります。ここでグランディ数が最初の０に戻りました。周期性を匂わせます。
＜石が６個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を２個取った「石が４個の局面」
①➁➂④⑤⑥ $${\rightarrow}$$ ①➁➂④
(case2) 石を３個取った「石が３個の局面」
①➁➂④⑤⑥ $${\rightarrow}$$ ①➁➂
の２局面。
(case1)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が４個の局面
$${\rightarrow}$$ 石が４個の局面のグランディ数は、$${(*4)}$$ より２
(case2)
$${\rightarrow}$$ 石を３個取る
$${\rightarrow}$$ 石が３個の局面
$${\rightarrow}$$ 石が３個の局面のグランディ数は、$${(*3)}$$ より１
(case1~2) より
$${\rightarrow}$$ 石が６個の局面から１手で移行できる局面のグランディ数は１と２
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその１と２を除く
$${\rightarrow}$$ その集合は $${\{0, 3, 4, 5, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は０
$${\rightarrow}$$ よって、石が６個の局面のグランディ数は０と決定・・・$${(*6)}$$
ここまでのグランディ数の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5 & 6\\
\hline
グランディ数 & 0 & 0 & 1 & 1 & 2 & 0 & 0
\end{array}
$$
となり、数列が「００」と初めと同じ並びが現れました。
＜石が７個の局面のグランディ数＞
このときの１手で移行できる局面は
(case1) 石を２個取った「石が５個の局面」
(case2) 石を３個取った「石が４個の局面」
の２局面。
(case1)
$${\rightarrow}$$ 石を２個取る
$${\rightarrow}$$ 石が５個の局面
$${\rightarrow}$$ 石が５個の局面のグランディ数は、$${(*5)}$$ より０
(case2)
$${\rightarrow}$$ 石を３個取る
$${\rightarrow}$$ 石が４個の局面
$${\rightarrow}$$ 石が４個の局面のグランディ数は、$${(*4)}$$ より２
(case1~2) より
$${\rightarrow}$$ 石が７個の局面から１手で移行できる局面のグランディ数は０と２
$${\rightarrow}$$ ０以上の整数の集合 $${\{0, 1, 2, 3, \cdots\}}$$ からその０と２を除く
$${\rightarrow}$$ その集合は $${\{1, 3, 4, 5, \cdots\}}$$
$${\rightarrow}$$ この集合の要素のうち最小の値は１
$${\rightarrow}$$ よって、石が２個の局面のグランディ数は１と決定・・・$${(*7)}$$
ここまでのグランディ数列の推移は
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
グランディ数 & 0 & 0 & 1 & 1 & 2 & 0 & 0 &1
\end{array}
$$
となります。実際、石の取り方が
①２個取る、②３個取る
のときのグランディ数は、次のように決定されます。
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots\\
\hline
グランディ数 & 0 & 0 & 1 & 1 & 2 & 0 & 0 & 1 & 1 & 2 & 0 & 0 & 1 & \cdots
\end{array}
$$
このときのグランディ数列は次のようになり
$${\underline{００１１２}００１１２００１１２００１１２ \cdots}$$
５つの数字「$${００１１２}$$」（下線部）が周期的に現れるので、周期５のグランディ数列となります。
さらに、石の取り方が
①２個取る、②４個取る、③７個取る
のときのグランディ数列は次のようになります。
$${００１１２２０３\underline{１０２}１０２１０２１０２ \cdots}$$
これは３つの数字「$${１０２}$$」（下線部）が周期的に現れるので、周期３のグランディ数列となります。このように頭からではなく、数列の途中から周期が現れる場合もあります。結果だけを示しておくので、実際に手を動かして計算してみてください。
５．『サブトラクションセット』について
ここで新しい定義を与えます。取れる石の数を集合で表し、その集合を『サブトラクションセット』とよびます。
例えば、取れる石の数を
①１個取る、②２個取る、③３個取る
としたときのサブトラクションセットは $${\{1, 2, 3\}}$$
取れる石の数を
①２個取る、②３個取る
としたときのサブトラクションセットは $${\{2, 3\}}$$
取れる石の数を
①２個取る、②３個取る、③７個取る
としたときのサブトラクションセットは $${\{2, 3, 7\}}$$ となります。取れる石の数を集合で表したものがサブトラクションセットです（注２）。
また、取れる石の数を『除去可能数』という場合もあります。取れる石の数を
①１個取る、②２個取る、③３個取る
としたときの除去可能数は１、２、３となります。
６．グランディ数についての重要な性質
ここでグランディ数について、次の性質があります。
定理１
グランディ数の値が０以外の局面のとき、先手が必勝戦略をもつ。 グランディ数の値が０の局面のとき、後手が必勝戦略をもつ。
例えば、 サブトラクションセットが $${\{1, 2, 3\}}$$ のときグランディ数は次の通りでした。
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots\\
\hline
グランディ数 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & \cdots
\end{array}
$$
すると、石の数が４の倍数のときはグランディ数は０なので、４の倍数のときに後手が必勝戦略をもちます。例えば残りの石の数が８個のときは
最初 ①➁➂④⑤⑥➆⑧
先手 １個取る $${\rightarrow}$$ 残りの石は７個
①➁➂④⑤⑥➆
後手 ３個とる $${\rightarrow}$$ 残りの石は４個（４の倍数）
①➁➂④
ここで先手に４の倍数を提示できるので
先手が１個取ると、後手が残りの３個すべてを取って後手の勝ち
先手が２個取ると、後手が残りの２個すべてを取って後手の勝ち
先手が３個取ると、後手が残りの１個すべてを取って後手の勝ち
と、最後に石を取った後手の勝ちとなります。
一方、石の数が７個のときはグランディ数は３（０以外）なので
最初 ①➁➂④⑤⑥➆
先手 ３個取る $${\rightarrow}$$ 残りの石は４個（４の倍数）
①➁➂④
ここで後手に４の倍数を提示できるので
後手が１個取ると、先手が残りの３個すべてを取って先手の勝ち
後手が２個取ると、先手が残りの２個すべてを取って先手の勝ち
後手が３個取ると、先手が残りの１個すべてを取って先手の勝ち
と、今度は先手の勝ちとなります。
もう一つ例を見てみましょう。サブトラクションセットが $${\{2, 3\}}$$ のときのグランディ数は次の通りでした。
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots\\
\hline
グランディ数 & 0 & 0 & 1 & 1 & 2 & 0 & 0 & 1 & 1 & 2 & 0 & 0 & 1 & \cdots
\end{array}
$$
すると、石の数が１０個のときはグランディ数は０なので
最初 ①➁➂④⑤⑥➆⑧⑨⑩
先手 ２個取る $${\rightarrow}$$ 残りの石は８個
①➁➂④⑤⑥➆⑧
後手 ３個とる $${\rightarrow}$$ 残りの石は５個（５の倍数）
①➁➂④⑤
ここで先手に５の倍数を提示できるので
先手が２個取ると、後手が残りの３個すべてを取って後手の勝ち
先手が３個取ると、後手が残りの２個すべてを取って後手の勝ち
と、最後に石を取った後手の勝ちとなります。これが冒頭でも述べた「５の倍数キープ」の必勝戦略です。
ただし、この場合はそれ以外の勝ち方もあります。石の数６個のときもグランディ数は０なので
(case1)
最初 ①➁➂④⑤⑥
先手 ２個取る $${\rightarrow}$$ 残りの石は４個
①➁➂④
後手 ３個取る $${\rightarrow}$$ 残りの石は１個
①
ルール上１個の石は取れないので、最後の石を取った後手の勝ちとなります。
(case2)
最初 ①➁➂④⑤⑥
先手が３個取る $${\rightarrow}$$ 残りの石は３個
最初 ①➁➂
後手が３個取る $${\rightarrow}$$ 残りの石は０個
と、最後の石を取った後手の勝ちとなります。冒頭で「５の倍数をキープ」すれば勝ちと言いましたが、それだけではない勝ち方もあります。
一方、石の数が７個のときはグランディ数は１（０以外）なので
最初 ①➁➂④⑤⑥➆
先手 ２個取る $${\rightarrow}$$ 残りの石は５個（５の倍数）
①➁➂④⑤
ここで先手に５の倍数を提示できるので
後手が２個取ると、先手が残りの３個すべてを取って先手の勝ち
後手が３個取ると、先手が残りの２個すべてを取って先手の勝ち
と、最後に石を取った先手の勝ちとなります（注３）。
結局このゲームの必勝パターンは、
１．自分にグランディ数が０でない局面が回ってきたら、相手にグランディ数が０の局面を回し、それをキープし続ける。
２．自分にグランディ数が０の局面が回ってきたら、相手が必勝手順から外れて自分にグランディ数が０でない局面が回ってくるまで粘り、それが回ってきたら１を実践する。
ということになります。あらかじめグランディ数の値を知っていることが鍵です。
さらにグランディ数列について、次のような性質があります。
定理２
サブトラクションセットが有限集合のとき、そのゲームのグランディ数列は必ず周期をもつ。
『有限集合』とは、その集合の中身が有限個となる集合です。この集合の中身のことを『要素』といいます。例えば、これまで出てきたサブトラクションセット $${\{1, 2, 3\}}$$、$${\{2, 3\}}$$、$${\{2, 3, 7\}}$$ は、どれも要素が有限個なのですべて有限集合です。一方、自然数の集合 $${\{1, 2, 3, 4, \cdots\}}$$ などは、要素が無限個あるので『無限集合』となります。
するとグランディ数列の周期は、サブトラクションセットが $${\{1, 2, 3\}}$$ のときは４、$${\{2, 3\}}$$ のときは５、$${\{2, 3, 7\}}$$ のときは３となるこことはすでにやったので、確かにいずれの場合も周期をもっています。
７．石取りゲームにおける「未解決問題」
ここで、次のような未解決問題があります。
未解決問題
「どんなサブトラクションセットに対しても、周期を与えるような式を見つけることができるか？」
これは、任意のサブトラクションセット $${S}$$ を代入したときに、必ずそのグランディ数列の周期を求めてくれる関数 $${f(S)}$$ が存在するか？という問題です。
例えばグランディ数列の周期は、サブトラクションセットが $${\{1, 2, 3\}}$$ のときは４だったので、$${f(S)}$$ に $${\{1, 2, 3\}}$$ を代入して
$${f(\{1, 2, 3\})=4}$$
サブトラクションセットが $${\{2, 3\}}$$ のときは５だったので、$${f(S)}$$ に $${\{1, 2, 3\}}$$ を代入して
$${f(\{2, 3\})=5}$$
サブトラクションセットが $${\{2, 3, 7\}}$$ のときは３だったので、$${f(S)}$$ に $${\{2, 3, 7\}}$$ を代入して
$${f(\{2, 3, 7\})=3}$$
さらにはより一般に、任意のサブトラクションセットが $${\{h_1, h_2, h_3, \cdots, h_n\}}$$ のときは、$${f(S)}$$ に $${\{h_1, h_2, h_3, \cdots, h_n\}}$$ を代入して
$${f(\{h_1, h_2, h_3, \cdots, h_n\})=h}$$
と周期 $${h}$$ を求めてくれる関数 $${f(S)}$$ が存在するか？という問題です。
先日のMATH POWER２０２２での企画で、この $${f(S)}$$ を求めるチャレンジを２日間かけて行っていました。番組内では細かく場合分けをして $${f(S)}$$ を導き出し、有意義な結果を得られたようです。個人的には１つの式で一発で出せる $${f(S)}$$ が存在するのか、また存在しないにしても何か美しい構造が $${f(S)}$$ に潜んであるのかどうか、いろいろ「妄想」するとロマンがどんどん広がっていきます。
８．終わりに
以上で『石取りゲーム』のルールと、必勝パターンを知る上での『グランディ数』、及びそのゲームに潜む未解決問題の解説を、なるべく一般の中学高校生でも分かるように解説してみました。専門家のチェックなど入っておらず不備があるかもしれませんが、随時加筆修正を加えていきます。
この内容を踏まえ、リアルタイムで見た方も、見れなかった方も、タイムシフト（アーカイブによる再放送）で『MATH POWER２０２２』を見てみてください。 この２日間の通し企画はある意味通常企画より面白い（？）。数学を考える楽しさを僕らに与えてくれます。$${f(S)}$$ の構造を美しい形で完全解明できれば恐らくフィールズ賞。フィールズ賞を獲るのはあなたかもしれません。
（注１）
実は、必勝パターンは１通りとは限らない場合もあります。
①２個取る、②３個取る
のルールでは、「５の倍数をキープ」する以外にも別の勝ち方もあります。それは後半に述べる『グランディ数』のところで解説します。
（注２）
本記事では扱いませんが、番組内で使われている記号の定義をここで与えます。
サブトラクションセット $${S}$$ が与えられたときの石取りゲームを『サブトラクションゲーム』とよび $${G(S)}$$ と表記します。例えば
サブトラクションセット $${\{1, 2, 3\}}$$ が与えられたサブトラクションゲームは $${G(\{1, 2, 3\})}$$
サブトラクションセット $${\{2, 3\}}$$ が与えられたサブトラクションゲームは $${G(\{2, 3\})}$$
サブトラクションセット $${\{2, 3, 7\}}$$ が与えられたサブトラクションゲームは $${G(\{2, 3, 7\})}$$ となります。
それを踏まえて今までのことをまとめると
$${G(\{1, 2, 3\})}$$ のときのグランディ数列は
$${\underline{０１２３}０１２３０１２３０１２３ \cdots}$$
下線部４つの周期性より周期４をもつ。
$${G(\{2, 3\})}$$ のときのグランディ数列は
$${\underline{００１１２}００１１２００１１２００１１２ \cdots}$$
下線部５つの周期性より周期５をもつ。
$${G(\{2, 3, 7\})}$$ のときのグランディ数列は
$${００１１２２０３\underline{１０２}１０２１０２１０２ \cdots}$$
下線部３つの周期性より周期３をもつ。
（注３）
石の取り方を間違えると、先手ではなく後手が勝ちになります。例えば石の取り方が
①２個取る、②３個取る
のとき、石が７個の局面のグランディ数は１（０以外）で先手に必勝戦略があります。
$$
\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
局面の石の数 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots\\
\hline
グランディ数 & 0 & 0 & 1 & 1 & 2 & 0 & 0 & 1 & 1 & 2 & 0 & 0 & 1 & \cdots
\end{array}
$$
しかし、次にように進むと
最初 ①➁➂④⑤⑥➆
先手 ３個取る $${\rightarrow}$$ 残りの石は４個
①➁➂④
後手 ３個取る $${\rightarrow}$$ 残りの石は１個
ルール上１個の石は取れないので、最後の石を取った後手の勝ちとなります。
このように、その局面で先手に必勝戦略があったとしても、取り方を間違えるとたちまち後手が勝ちになるので、「必勝戦略」とはどのように石をとっても勝ちになるという意味ではなく、戦略をもって最善で石を取っていった場合に勝ちになる、という意味です（当たり前の指摘ですが一応念のため）。
この記事が気に入ったらサポートをしてみませんか？