数理解析研究所講究録
第 1785 巻 2012 年 45-50

45

数式処理システムを用いた組み合わせゲームの研究と教育への応用
宮寺 良平

関西学院高等部 *RYOHEI MIYADERAKWANSEI GAKUIN
要約

この論文では組み合せゲームの一種であるチョコレート問題について考える．チョコレート問題
は数学関連の関数を多く持つ数式処理システムには適している．今回紹介するのは、 L-state がやや複雑な規則性を持っているチョコレート問題である．その問題の特徴を理解していただくために、 既に発表済みのL-state の公式を持つチョコレートと比較して考える．
研究全般において、 数式処理システム Mathematica に大きく依存しており、 その計算機能とプログラム機能が本質的に寄与している．

1

チョコレートゲームの紹介

まずチョコレートゲームを定義する．定義を理解するためには、常に具体的なチョコレートの形を見ながら定義を読む必要がある．まず初めには、 図 11 のチョコレートを見ながら読んでいただきたい．
定義 1

薄いグレーの部分は甘く、濃いグレーの部分は苦くて食べることができないチョコレートがある．このチョコレートを 2 人のプレイヤーが交互に、切り取り線に沿って 2 つに割り、 濃いグレーの部分を含む方を残して、薄いグレーだけの部分を食べる．その結果として食べた部分は消去される．最後に苦い部分を残されたプレイヤーが負けである．
定義 1 においては、 最後に苦くないチョコを割って食べた者が勝っ．苦いチョコを残されたものは食べることができない．最後に食べた者が勝つので、 ゲーム理論では正規形ゲームとよばれるものである 図 11のチョコレートを考える
縦と横のブロックの数を使ってのチョコレートと呼ぶことにする．切り取り線は、 白い部分で、 縦か横に切ることができる．切るとチョコレートの図形が 2 つのパートに分割さ$5\cross 3$れるが、 左下の濃いグレーの部分を含んだ部分はそのままにして、 もう 1 つのパートは食べてしまう．結果として、 縦に切るとすれば、 $5\cross y(1\leq y<3)$ のチョコレートが残る．例えば、 縦の 1 列を切り取ると、

図 12 のチョコレートが残る．横に切るとすれば $x\cross 3(1\leq x<5)$ となり、 例えば、 横の 1 列を切り取ると、 図 13, 横の 2 列を切り取ると、 14 のようになる．このチョコレートゲームをプレーする場合に現れる

チョコレートの形は $x\cross y(1\leq x<5)(1\leq y<3)$ となる．

’miyadera1272000@yahoo.co.jp

46
図 1.1
$5\cross 3$$\#\infty$

灘$&$nu\infty$$\mathfrak{B}@\mathscr{R}$$\blacksquare$$\mathfrak{X}infty$$$W$\blacksquare$$\mathfrak{X}sim$$\blacksquare\*$$\delta$$\blacksquare X$$\blacksquare$

図 1.2

図 1.3

図 14$5\cross 2$$4\cross 3$$3\cross 3$

これを使ってゲームするとすれば、 先手と後手のどちらが有利であるかを考える．実はあなたが先手でプレーすれば勝つことができる．方法は簡単である．図 14 とすれば良い．ここから相手は $x\cross 3(1\leq x<3)$か $3\cross y(1\leq y<3)$ に移る．そうすればあなたは $x\cross x(1\leq x<3)$ か $y\cross y(1\leq y<3)$ に移ればよい．

すなわち相手がどのようにプレーしても、 あなたは縦と横のブロック数を同じすれば、 最終的に 1$\cross 1$のチョコの状態にして、 相手に苦くて食べれない部分を残して勝てる．

定義 2
チョコレートゲームにおいては重要な 2 つのポジション (座標) がある．
$(a)$あるチョコレートの状態が $W-Stat\alpha$ (Winning poeition) であるとは、 この状態からゲームを始めたプレイヤーは、 これ以後正しい手を選ぶ限り、 必ず勝つということである．
$(b)$あるチョコレートの状態が L-States (Losing poeition) であるとは、 この状態からゲームを始めたプレイヤーは、 相手が正しい手を選び続けると、 どんな手を選んでも、必ず負けるということである．

注意 1

W-state から始めるプレイヤーがミスをすると負ける可能性があるし、 L-state から始めるプレイヤーは、相手がミスをすると勝っ可能性がある．

L-S tates は P-position ( previous-player-winning posi tion) と呼ばれることもある．また、 W-States は$a$

N-position (an next-player-winning position) と呼ばれることもある．
次に考えるのは、長方形ではなく、三角形のチョコレートである．このタイプのチョコレート問題は著者と関西学院高等部の生徒によって作られた新しい問題である．
図 15 のチョコレートは [1] で既に研究されたものである．しかし良く似た形の図 16 のチョコレートは新しいチョコレートである．図形の下に書いてある数字の組はチョコレートの座標である．これについては後で説明する．

図 1.5

図 16{3, 6, 3}{3, 6, 6}

これらのチョコレートの状態を表す座標を導入する．図 15 はチョコレートを左上から右下に向う線に沿って、 苦いチョコの左を最大 3 回、 左上から右下に向う線に沿って苦いチョコの右を最大 6 回、 右上から左下に向う線に沿って苦いチョコの位置よりも右側を最大 3 回切ることが出来る．したがって座標は {3,6,3}

47とする．

図 16 はチョコレートを左上から右下に向う線に沿って、 苦いチョコの左を最大 3 回、 左上から右下に向う線に沿って苦いチョコの右を最大 6 回、右上から左下に向う線に沿って苦いチョコの位置よりも右側を最大6 回切ることが出来る．したがって座標は {3,6,6} とする．
以上のように、 チョコレートの座標は、 チョコレートをそれぞれ 3 つの方向に切ることができる最大回数で決まる．

本論文においては、 これらのタイプのチョコレート問題を中心テーマとして扱うが、構造は同じままで任意の $x,$ $y,$ $z\in Z_{\geq 0}$ に対して、座標 $\{x, y, z\}$ となるチョコレートを考える．

2L-state が簡単な公式になるタイプのチョコレートは非負正数の集合とする．ここでは図 15 のチョコレートを考える．チョコレートを切った場合にっいて例をあげる．図の下に書いている番号はチョコレートの状態を表す座標である．
$Z_{\geq 0}$

図 2.1

図 22{2, 4, 2}{1, 6, 3}

すぐにわかることだが座標は、 $y\geq 2z$ を満たす．ただし、 $y,$$z\in Z_{\geq 0}$. このように座標が不等式を満たす

ようなチョコレートは著者達が作り出した問題である．
チョコレート問題において重要なニム和という概念を定義する．
定義 3$x,$ $y\in Z\geq 0$とし、 2 進数表示して、 $x= \sum_{i=0}^{n}x_{i}2^{i},$ $y= \sum_{i=0}^{n}y_{i}2^{i}$ とする．なおここでる．このときニム和$x\oplus y$$x_{i},$$y_{i}\in\{0,1\}$とすを次のように定義する．
$x \oplus y=\sum_{i=0}^{n}w_{i}2^{i}$

ここで $w_{i}=x_{i}+y_{i}$ (mod 2),(1)

はを 2 で割った余りである．とする．すなわちニム和は計算機科学の分野では排他的論理和と呼ばれることが多い．
$w_{i}$$x_{i}+y_{i}$ニム和を使うと、 図 15 のチョコレートに関しては L-state を特徴づけることができる．
定理 4$A_{1}=\{\{x, y, z\};x, y, z\in Z_{\geq 0}, y\geq 2z$$x\oplus y\oplus z\neq 0\}$かつ $x\oplus y\oplus z=0\},$ $B_{1}=\{\{x, y, z\};x,$ $y,$ $z\in Z_{\geq 0},$ $y\geq 2z$ かつとする． は図 15 チョコレートの L-state の集合で、$A_{1}$$B_{1}$は W-state の集合である．

この定理の証明は [1] にある．

3

L-state が簡単な公式にならないタイプのチョコレート

ここでは図 16 のチョコレートを研究する．チョコレートを切った場合について例をあげる．図の下に書いている番号はチョコレートの状態を表す座標である．

48

図 31

図 32

{2, 3, 3}{3, 6, 1}

すぐにわかることだが座標は、 $y\geq z$ を満たす．
$Larrow state$ を表す法則や公次は図 16 のチョコレートの L-state を計算する Mathematica プログラムである．
式を見つけるためには、 計算機によってできるだけ多くの L-state のデータを出し、 それを整理しながら法則を見っけるのが一般的な方法である．

ss $=100;k=2$ ;al$=$.

.

$\{a,$, ss}], 2 ;ss}, $\{b,$ , ss},
Flatten Table $[\{a,$ $b,$
Select $[al, (1/k)(\#[[2]])>=\#[[3]] \ ]$ ;allcases
move $[z_{-}]$ $:=$ Block $[\{p\},$ $p=z$ :Union [Table $[\{p[[1]],$ $p[[2]],$ $t3\},$ $\{t3,0,$ $p[[3]]-1\}]$ ,Table $[\{p[[1]], t2, Min [Floor [(1/k)(t2)], p [[3]]]\}$ , $\{t2,0$ ,$c\}$$[$$0_{*}$$0$$\{c$$0$$]$$=$$p[[2]]-1\}]$ ,Table $[\{t1,$ $p[[2]],$ $p[[3]]\}$ , {tl, $0,$ $p[[1]]-1\}]]]$ ;$:=M$ in [Complement [Range
Length [L]], $L]$ ] ;Mex
Gr [pos-] $:=$ Gr [pos]Mex [Map [Gr, move [pos]]] ;Select [allcases, Gr [$] $==0$ &] ;ppositionl$[L_{-}]$$[0_{*}$$=$$=$

上のプログラムによって L-state のデータを作り、 それらを第 1 座標で整理することで次のような式によって、 データを表すことが出来た．ただし、 数学的な証明がまだ未完成であるために、 予想として扱う．
AA $[n_{-}]:^{=}$
Union Jo in [$[$

Table $[\{6n-1,4n+2k-1,4n-4k- l\}, \{k, 0, n-1\}]$ ,Table $[\{6 n- 1.4n+2k, 4n-4k-2\}, \{k, 0, n-1\}]$ ,Table $[\{6n-1,6n+2k-1,4k\}, \{k, 0, n-1\}]$ ,Table $[\{6n-1,6n+2k, 4k+1\}. \{k. 0, n-1\}]]]$ :$BB[n_{-}];=$

Union $[Join[Table[\{6n, 4n+2k. 4 n- 4k\}, \{k, 0, n\}]$ ,Table $[\{6n, 4n+2k+1,4 n- 4 k-3\}, \{k, 0, n-1\}]$ ,Table $[\{6n, 6n+2k+1.4k+2\}, \{k, 0, n-1\}]$ ,Table $[\{6n_{*}6n+2k+2,4k+3\}, \{k, 0, n-1\}]]]$ ;CC $[n_{-},m_{-}]:^{=}$
Union Jo in [Table $[\{6n+1,4n+2k+1,4n-4k-1\}, \{k, 0. n-1\}]$ ,Table $[\{6n+1,4n+2k+2,4n-4k-2\}, \{k, 0, n-1\}]$ ,Table $[\{6n+1,6n+2k+1,4k\}, \{k, 0, n\}]$ ,Table $[\{6n+1,6n+2k+2,4k+1\}, \{k, 0, n-1\}]$ ,Table $[\{6n+1, k+8n+2, k+4n+1\}, \{k, 0, n+m\}]]]$ ;$[$$DD[n_{-}]:=$

Union Jo in [Table $[\{6n+2,4n+2k+1,4n-4k+1\},$[$\{k, 0, n\}]$ ,$Table[\{6n+2,4n+2k+2,4n-4k\}, \{k, 0, n\}]$ ,Table $[\{6n+2,6n+2k+3,4k+2\}, \{k. 0, n-1\}]$ ,Table $[\{6n+2,6n+2k+4,4k+3\}, \{k, 0, n-1\}]]]$ ;EE $[n_{-}]:=$
Union Jo in [$[$

Table $[\{6n+3,4n+2k+2,4n+2-4k\}, \{k, 0. n\}]$ ,Table $[\{6n+3,4n+2k+3,4n-4k-1\}, \{k, 0. n-1\}]$ ,Table $[\{6n+3,6n+2k+3,4k\}, \{k, 0, n\}]$ ,Table $[\{6n+3_{*}6n+2k+4,4k+1\}. \{k, 0, n\}]]]$ ;49
FF $[n_{-},m_{-}]$ $;=$
Union [Join [Table $[\{6n+4,4n+2k+3,4n-4k+1\}, \{k, 0, n\}]$ ,Table $[\{6n+4,4n+2k+4,4n-4k\}, \{k, 0, n\}]$ ,Table $[\{6n+4,6n+2k+5,4k+2\}, \{k, 0, n\}]$ ,Table $[\{6n+4,6n+2k+6,4k+3\}, \{k, 0, n-1\}]$ ,Table $[\{6n+4, k+8n+6, k+4n+3\}, \{k, 0, n+m\}]]]$ ;次のような予想ができる．
$\bigcup_{n\in Z\geq\text{。}}(AA[n]\cup BB[n]\cup CC[n, m]\cup DD[n]\cup EE[n]\cup FF[n, m])$ はL-state の集合となる

この予想の証明に関しては、 まだ完成していないが、大まかな方法論だけはできている．それを紹介する．
ただし、以下のような議論を精密にして、 なお読者が理解できるようにすることはかなりの工夫が必要であり、 まだ未完成である．

図 33証明のポイント

図 33 はこのチョコレートゲームに現れる state を表示したものであるが、 第 1 座標を省いて、 第 2 座標と第 3 座標で点をプロットしている．横軸は第 2 座標の 座標で、 縦軸は第 3 座標の 軸である．点線は直線 $z=y$ である．各点は、 直線で結ばれた点の集合は L-state の点の第 2, 3 座標をプロットしたものである．
$z$

$y$

そしで、 同じ濃度を持つ色の点同士は、 第 1 座標が同じものである．1 番色の濃い点の集まりは第 1 座標が1 で、 順に、 色の薄い点の集まりになっていくが、 第 1 座標は 2, 3, 4, 5, 6 となっていく．

点で結ばれていない点は、 すべて第 1 座標が 6 である W-state である．
ここで重要なことは、 W-state からうまく動くと L-state へ行くことである．
例えば {6,10,7} は第 2 座標の を減らすことで、 {6,4,4} へ行くことができる。 この図においては、 第 1 座標は書いていないから、 {10,7} において、 を 4 に減らすと、 図形の性質から も 4 となり、 {4,4} となる．
これは不等式 $y\geq z$ を使うと考えても良い．{6,6,3} は、 を減らして {6,6,0} へいくことができる。
$y$$z$$y$$z$

このように、 第 1 座標が 6 であるもののうちで、 第 2, 3 座標を減らして L-state へ行くことができるのは、
第 1 座標が 6 である L-state の右に位置する第 1 座標が 6 である W-state である．

50
次に第 1 座標が 6 である L-state の左に位置する W-state を考える．それらの点の場合は、 第 1 座標を減らすことで L-state へ行くことができる．その理由は図 34 のように、 L-state は三角形の形に点を敷き詰めていくからである．結果として、$\{6.3_{:}2\}$は、 {1.3.2} ’ 行くことができる。 次に L-state からはどのように動$\backslash$いても W-state へ行くことが重要である．そのようになる理由を考える．

まず、 $\{x,y.z\}$ から移動するとき、$x$を減らすと、 $L_{}state$ へは行かない．何故なら、 図 34 を見てもわかる

ように、 第 1 座標の異なる L-state 同士は、 第 1 座標を省いて平面にプロットしても重ならないからである．
を減らすと、 L-state へは行かない．何故なら、 図 3.4 を見てもわかるように、 第 1 座標の同じ L-state 同$y$

士は、 第 2 座標に関しても同じものはないからである．
を減らすと、 L-state へは行かない．何故なら、 図 3.4 を見てもわかるように、 第 1 座標の同じ L-state 同$z$$\pm$は、 第 3 座標に関しても同じものはないからである．

図 34

この研究は大阪大学の大学院生である峰松大介氏、 関西学院の大学生である稗田卓人氏、 高校生である藤井亮平氏、 内藤瑠一郎氏のアイデアに依る部分が多かった．ここで感謝したい．

参考文献[1] Ryohei Miyadera, Shunsuke Nakaniura and Ryo Hanafusa.New Chocolate Games -Variants of theGame of Nim-,Proceeding of Annual International Conference onComputational Mathematics. Computational Geometry Statistics 2012.