1  序文

　チョコレートゲームは，一箇所に苦いチョコレートを配置した板状のチョコレートにおいて，2人のプレイヤが互いに縦もしくは横一直線にチョコレートを2つに分割して，苦いチョコレートを含まない方を食べる．そして苦いチョコレートを相手に残せば勝ちとなる．図1.1のチョコレートゲームは，山の高さがそれぞれ3,3,2の3つの山をもつニムと数学的に同値である．ここで，カットできる最大回数が，苦い部分の左側で3，上側で3，右側で2となる．このとき，座標{3,3,2}と表す． 本稿では，図 1.2〜図1.4のような階段状のタイプのチョコレートを研究している．このタイプでは，垂直方向のカットにより，水平方向に切ることができる回数が減る可能性があり，長方形チョコレートゲームや，3つの山の石取りゲームとは数学的性質が異なる．

図1.1のような長方形チョコレートゲームは各方向に切ることができる最大数によって座標{x,y,z}と表すことができ，3つの山の石取りゲームも座標{x,y,z}と表すことができるが，これらは数学的に同値であるから，良く知られている3つの山の石取りゲームの理論によってGrundy数はx ⊕ y ⊕ zで表すことができる．しかし階段状のタイプのチョコレートにおいては，Grundy数を求めることが簡単でないものが多い． 私達のグループは国際的な数学専門誌 [1] において，Grundy数がx ⊕ y ⊕ zで表されるためにチョコレートの形状が満たすべき十分条件を提出した．なお，Grundy数がx ⊕ y ⊕ zという形にならないチョコレートの形状については，例としては図1.5と図1.6のチョコレートがある．

従って，Grundy数がx ⊕ y ⊕ zで表されるためにチョコレートの形状が満たすべき必要十分条件が重要な問題になる．本論文においては，数学専門誌[1]掲載論文を一般化したものである必要十分条件を証明する．その論文で使用している数学は,高校レベルを殆ど越えていないが, かなり独特な証明と計算が多い．証明方法の難しさは，私の属する研究グループがこの分野の開拓者的な役割をしたため，この分野はまだ標準的な証明方法が確立されていない．そのために, 普通の数学のテキストに存在しないような証明方法が大半を占める．そのために専門の数学者であっても，理解するのが難しい可能性が大きい．黒板を使って口頭で説明することで証明を要点を理解してもらうことはそれほど難しくないが，論文として書くと難解になってしまう．

ただし，数学で博士号を持つ顧問の先生と共に綿密な添削を何度も繰り返したので，数学的厳密さは保証できる．

以下，Z≥0を非負整数の集合とする．また xi ∈ {0,1}と書くときは，xiは0か1であるという意味である．

例 1.1   チョコレートゲームの例をあげる．チョコレートゲームでは，座標を{x,y,z}　ただし(x,y,z ∈ Z≥0)と表現する．詳しくは後で説明を行う． なお，図1.1のチョコレートの座標は{3,3,2}，図1.2の座標は{4,4,9}，図1.3の座標は{4,3,13}，図1.4の座標は{4,3,13}である．
図 1.1   {3,3,2}
図 1.2   {4,4,9}


図 1.3   {4,3,13}

図 1.4   {4,3,13}


図 1.5  

図 1.6  

チョコレートゲームは組み合わせゲームであり，詳しくは[4]を参照していただきたい．

定義 1.1   x,yを非負整数とし，2を基数として書くと，x = ∑i=0n xi 2i,y = ∑i=0n yi 2i (xi,yi ∈ {0,1})となる． ニム和x ⊕ yを以下のように定義する．
x ⊕ y = 
n
∑
i = 0
 wi 2i,     (1)
ここで，wi=xi+yi (mod 2)である．

チョコレートゲームには以下の2つの状態があり，すべての状態はどちらかに属する．

定義 1.2   (a) 先手必勝手(N -ポジション) とは，後手がどのような戦略をとっても，先手がうまくプレイすれば必ず勝てる状態．
(b) 後手必勝手(P-ポジション)とは，先手がどのような戦略をとっても，後手がうまくプレイすれば必ず勝てる状態．
定義 1.3   GとHを不偏ゲームとする．この2つのゲームの直和G+Hは，プレーの度に，プレイヤーがGまたはHのいずれかを選んでプレーすることによって成立するゲームである．

図1.2から図1.4において，各チョコレートゲームは，苦い部分の左側のチョコレートと，苦い部分の右側のチョコレートの直和であると考えることができる．

定義 1.4   ゲームGの状態pに対して，一手で移動できる集合をmove(p)と表記する．
注意 1.1   moveの例は，例1.4を見ていただきたい．
定義 1.5   (i) mex関数とは，非負整数からなる集合Sに含まれていない 数字の中で，最も小さい非負整数を出力する関数である．
(ii) Grundy数とは与えられた状態から一手で移動できる全ての状態におけるGrundy数からなる集合に含まれていない最小の非負整数であり，Grundy数をGとすると，以下のように再帰的に定義される．
G(p) = mex{G(h): h ∈ move(p)}

mexから次の補題が導かれる．

補題 1.1   x ∈ Z≥ 0とし， k=1,2,...,nに対して，yk ∈ Z≥ 0とする．そのとき(i)と(ii)は同値である．

(i) x = mex({yk,k=1,2,...,n}).
(ii) 全てのkに対してx ≠ ykであり，u < xとなるu ∈ Z≥ 0に対して，u = ykとなるkがある．

証明. 定義 1.5 から直接導かれる(mexの定義)．

補題 1.2   Sを集合とし， {1,2,3,...,m−1} ⊂ Sであるとする．そのとき，mex(S) ≥ mが成り立つ．

証明. 定義 1.5のmexの定義から直接導かれる．.

Grundy数が強力なツールであることは，次の結果からわかる．

定理 1.1   G，Hを不偏ゲームであるとする．GGと GHをそれぞれ，GとHのGrundy数だとすると，次のことが成り立つ．
(i) Gの全てのポジションgに対して，gがP-ポジションとなるのは，GG(g)=0のときに限る．
(ii) G+Hのポジション{g,h}におけるGrundy数は，GG(g)⊕ GH(h)となる．

この定理の証明は，[4]を参照していただきたい．
一般的なチョコレートを扱うと複雑になりすぎるため，ここでは高さが一定の条件に従って増加する階段状のチョコレートだけを研究する．

定義 1.6   関数fが以下の2つの条件を満たすとする．
(i) t ∈ Z≥0に対して，f(t)∈ Z≥0が成り立つ．
(ii) fは単調増加である．つまり， u ≤ vを満たすu,v ∈ Z≥0に対して，f(u) ≤ f(v)となる．
定義 1.7   y,zを非負整数としy ≤ f(z)とすると，チョコレートはz+1列で構成され， 0列目は苦いチョコレート，i列目の高さはt(i) = min(y, f(i)) +1である．そのチョコレートをCB(f,y,z)と表記する．
y,zはそれぞれ水平方向，垂直方向に線に沿って一直線に切ることができる最大回数を表す．
例 1.2   CB(f,y,z)の例．

CB(f,3,13) f(t) = ⌊ t/4⌋

図 1.7  

CB(f,4,9) f(t) = ⌊ t/2⌋

図 1.8  

CB(f,2,9) f(t) = ⌊ t/2⌋

図 1.9  

CB(f,8,31) f(0)=f(1)=0かつt > 1に対して，f(t) =2⌊ log2t ⌋ −1 .

図 1.10  

定義1.6の条件を満たす関数fを固定して考えるときは，fを略して，CB(f,y,z)を{y,z}という座標で表す．

例 1.3   f(t) = ⌊ t/2⌋となるチョコレートの例．


CB(f,2,5) {2,5}

図 1.11  

CB(f,1,3) {1,3}

図 1.12  


CB(f,0,5) {0,5}

図 1.13  

CB(f,1,5) {1,5}

図 1.14  

関数fを固定して考える．CB(f,y,z)の各座標{y,z}において，そこから一手で移動できるポジションの座標をすべて表す集合をmovef({y,z})と書く．これは定義1.4で定義されたmoveの特別な場合である．階段状のチョコレートでは垂直方向のカットにより(z座標が減って)，水平方向に切ることができる回数が減る可能性があるが，このことは下の定義では， 第2座標がmin( y, f(w))となることで表されている．

定義 1.8   y,z ∈ Z≥ 0に対して，movef({y,z})={{v,z }:v<y } ∪ { {min(y, f(w)),w }:w<z }, (v,w ∈ Z≥ 0).
例 1.4   関数f(t) = ⌊ t/2⌋を固定して考える．例1.3のチョコレートを例に使う．

{y,z}={2,5}の位置から開始したとする．第1座標であるyを減らすと，{1,5}, {0,5}へ行けるので， {1,5}, {0,5} ∈ movef({2,5})となる．

{y,z}={2,5}の位置から第2座標であるzを5から4に減らすと，第1座標であるyは，min(2, ⌊ 4/2 ⌋ )=min(2,2)=2のままである．従って，{2,4} ∈ movef({ 2,5 }) {y,z}={2,5}の位置から第2座標であるzを5から3に減らすと， 第1座標であるyは，min(2, ⌊ 3/2 ⌋ )=min(2,1)=1となる．従って， {1,3} ∈ movef({ 2,5 })

{y,z} = {1,3}の位置からはどのようにしても{0,5} へは行けないので，{0,5} ∉ movef({1,3})である．

本論文の目的として，チョコレートCB(f,y,z)のGrundy数がG({y,z}) = y ⊕ zとなるためにfが満たすべき必要十分条件を求めるが，そのための方法として，図 1.2,図1.3のように苦い部分の右側にCB(f,y,z)，左側に高さ1のチョコレートをおいた直和を考える．左側の高さ1チョコレートを垂直方向にカットできる回数をxとすると，このチョコレートは{x,y,z}と表すことができる．このチョコレートの P-ポジションがx⊕ y⊕ z=0となる場合であることを示し，結果的にCB(f,y,z)のGrundy数がG({y,z}) = y ⊕ zとなることを導く．

G({y,z})=y ⊕ zとなるチョコレートゲーム next