2.1 十分条件

 この小節ではGrundy数 G({y,z}) = yzとなるチョコレートの十分条件について述べる.

定義 2.1   定義1.6を満たす関数をhとおく.このhは次の条件を満たす.
(a)  あるz,zZ≥ 0 と,ある自然数iにおいて
⌊ 
z
2i
⌋ = ⌊ 
z
2i
⌋     (2)
とすると,
⌊ 
h(z)
2i−1
⌋ = ⌊ 
h(z)
2i−1
⌋     (3)
となる.
注意 2.1   定義 2.1 の条件 (a) は以下に示す条件 (b)と等しい.
(b) 各k = 0,1,...,n に対してzk,yk ∈ {0,1}とおく. また,
h(
n
k = 0
 zk 2k)=
n
k = 0
 yk 2k
とおく. そうすると,各k=0,...,i−1に対して定義されたzk ∈ {0,1}に対して, 各 k=0,...,i−2に対して定義された yk ∈ {0,1}が存在して,次の式が成立する.
h(
n
k = i
 zk 2k + 
i−1
k = 0
 zk 2k) = 
n
k = i−1
 yk 2k + 
i−2
k = 0
 yk 2k.

ただしiは自然数とする.

補題 2.1と補題 2.2において,定義 2.1の条件 (a)を満たす関数の例を与える.

補題 2.1   ある自然数 k においてh(z)=⌊ z/2kとする. このとき, h(z)は,定義 2.1を満たす.

証明. 定義 2.1の条件の対偶を証明する.

等式 (3)が成立しないとする. そのとき,ある uZ≥ 0と,ある自然数 iが存在して,

⌊ 
⌊ 
z
2k
  ⌋
2i−1
⌋ = u < u+1 ≤  ⌊ 
⌊ 
z
2k
  ⌋
2i−1
⌋     (4)

となる. 等式( 2)が成立しないことを証明する. 不等式( 4)より,

⌊ 
z
2k
  ⌋ ≤ u2i−1+2i−1−1 < (u+1)2i−1 ≤  ⌊ 
z
2k
  ⌋  

が導かれる. したがって

z ≤  2k(u2i−1+2i−1−1)+2k−1 < 2k(u+1)2i−1 ≤  z.     (5)

不等式(5)より,

z
2i
 ≤  k(u+1)−
1
2i
 < k(u+1) ≤  
z
2i
 

が導かれる. したがって

⌊ 
z
2i
  ⌋ < k(u+1) ≤  ⌊ 
z
2i
  ⌋.  

ここで等式(2)が成立しないことが示された.


補題 2.2   h(0) = h(1)=0とし,z ≥ 2を満たすzZ≥ 0に対して,h(z)=2log2z⌋−1とおく.このとき h(z)は定義2.1の条件を満たす.

. 定義 2.1の条件の対偶を証明する. 等式( 3)が成立しないとする. 自然数 iに対して,

⌊ 
2⌊ log2z⌋−1
2i−1
⌋  <    ⌊ 
2⌊ log2z⌋−1
2i−1
⌋.     (6)

z = 2n+m , z=2n+mとおく.ここで,n, nZ≥0, 0 ≤ m,m < 1である. そのとき不等式 (6)より,

⌊ 2ni  ⌋ < ⌊ 2ni  ⌋.     (7)

不等式(7)より,

     
    n − i ≥ 0           (8)
     かつ        
    n+1 ≤ n.            (9)

不等式(8) , (9) より

⌊ 
z
2i
  ⌋ =  ⌊ 2n+mi  ⌋ <  2ni ≤  ⌊ 2n+mi  ⌋ = ⌊ 
z
2i
  ⌋.  

これは等式(2) が成立しないことを示している.


この小節の残りでは hは定義2.1を満たす関数であると仮定する.

補題 2.3  
h(
n
k = 0
 zk 2k) ≥ 
n
k = 0
 yk 2k     (10)
とする. そのとき,任意の自然数iに対して,
h(
n
k = i
 zk 2k) ≥ 
n
k = i−1
 yk 2k.

. h(∑k = 0n zk 2k) = ∑k = 0n uk 2kとおく. ここで uk ∈ {0,1}である. そのとき, 不等式(10)より,

n
k = 0
 uk 2k ≥ 
n
k = 0
 yk 2k

故に

n
k = i−1
 uk 2k ≥ 
n
k = i−1
 yk 2k.      (11)

k = 0,1,2,...,i−1に対して zk = 0とおく. 不等式( 11), 定義2.1 ,注意 2.1より,k=0,...,i−2 に対して yk が存在して,

     
   
 h(
n
k = i
 zk 2k) = h(
n
k = i
 zk 2k + 
i−1
k = 0
 zk 2k
 
  =
 
n
k = i−1
 uk 2k + 
i−2
k = 0
 yk 2k ≥ 
n
k = i−1
 uk 2k ≥ 
n
k = i−1
 yk 2k.
 


補題 2.4   k=0,1,...,nに対してpk,qkZ≥0が定義されているとする.このとき次の(i),(ii)が成り立つ.
(i) ある自然数 i に対して,
h(
n
k = i
 pk 2k) < 
n
k = i−1
 qk 2k     (12)
が成立するとき,
h(
n
k = 0
 pk 2k) < 
n
k = i−1
 qk 2k.
(ii)
h(
n
k = 0
 pk 2k) ≥ 
n
k = i−1
 qk 2k
とすると,
h(
n
k = i
 pk 2k) ≥ 
n
k = i−1
 qk 2k

となる.

. ( i)を証明する.h(∑k = 0n pk 2k)= ∑k = 0n rk 2kとおく.ここでrk ∈ {0,1}とする. そのとき,注意 2.1より, k=0,1,2,...,i−2に対してrkが存在して, h(∑k = in pk 2k + ∑k = 0i−1 0 × 2k) = ∑k = i−1n rk 2k+∑k = 0i−2 rk 2k. そのとき, 不等式 (12)より,

n
k = i−1
 qk 2k > 
n
k = i−1
 rk 2k+
i−2
k = 0
 rk 2k

を得る. 故に不等式( 13)または関係(14)を得る.

qn > rn.     (13)

あるjZ≥0 が存在して,
i−1 ≤ jn , k = j+1,j+2,...,n に対して

qk = rk が成り立ち, qj > rjとなる.      (14)

そのとき,不等式(13)または関係(14)より, ∑ k = i−1n qk 2k > ∑k = i−1n rk 2k+∑k = 0i−2 rk 2k

n
k = 0
 rk 2k=h(
n
k = 0
 pk 2k).

(ii)は(i) の対偶である.

補題 2.5  
h(
n
k = i
 pk 2k) < 
n
k = i−1
 qk 2k+2i−1     (15)
とすると,
h(
n
k = i−1
 pk 2k) < 
n
k = i−1
 qk 2k+2i−1.

.k = i−1n+1 qk 2k = ∑k = i−1n qk 2k+2i−1pn+1=0とおく.そのとき, 不等式(15)より, h(∑k = in+1 pk 2k) < ∑k = i−1n+1 qk 2kを得る. 補題 2.4の(i)により h(∑k = i−1n pk 2k) ≤ h(∑k = 0n+1 pk 2k) < ∑k = i−1n+1 qk 2k =∑k = i−1n qk 2k+2i−1となり,この補題は示された.

補題 2.6   xyz ≠ 0 かつ
y ≤ h(z) とする (16)
そのとき以下の命題のうち少なくとも1つは成り立つ.
(1) u<xを満たすあるuZ≥ 0に対してuyz= 0.
(2) v<yを満たすあるvZ≥ 0に対してxvz= 0.
(3) w<z, yh(w)を満たすあるwZ≥ 0 に対してxyw= 0.
(4) v<y,w <z, v=h(w)を満たすあるv,wZ≥ 0に対してxvw= 0.

. x= ∑k = 0n xk 2k, y= ∑k = 0n yk 2k, z= ∑k = 0n zk 2kとする.n=0ならばこの補題は自明であるからn ≥ 1と仮定する.

ある非負整数sが存在して,

xns−1 + yns−1 + zns−1 ≠ 0  (mod  2)     (17)

となり,i = n,n−1,...,nsに対してxi + yi + zi = 0 (mod 2)が成り立つとする.
Case (i) xns−1=1となる場合. このとき, u = ∑i=1nui2iを次のように決める.まずi=n,n−1,..., ns に対してui=xiとし,uns−1=0<xns−1として,i=ns−2,ns−3,...,0に対してui=yi+zi ( mod 2 )と決める. このとき uyz = 0かつu<xとなって(1)が成り立つ.
Case (ii) yns−1=1となる場合は(i)で使った方法と同じようにして, v<yとなるようなvZ≥ 0があってxvz = 0となり,(2)が成り立つ.
Case (iii)

zns−1 =1     (18)

である場合.i = n,n−1,...,nsに対して,

wi = zi     (19)

として,各i=ns−1,...,0に対して,wi = xi + yi (mod 2) とする. 不等式( 17)と等式(18)より, wns−1 =xns−1+yns−1 = 0 (mod 2)を得る. 故に

wns−1=0 < 1 = zns−1.     (20)

このとき2つのSubcaseに分けて考える.
Subcase (iii.1) もしyh(w)ならばこの補題の(3) は示される.
Subcase (iii.2) 次に

y > h(w)     (21)

となる場合を考える. 不等式( 16)より ∑k = 0n yk 2kh(∑k = 0n zk 2k)となる.故に 補題 2.3 と 等式(19)より

n
k = ns−1
 yk 2k ≤  h(
n
k = ns
 zk 2k)=h(
n
k = ns
 wk 2k) ≤ h(w).     (22)

不等式(22) と 不等式(21)より

     
n
k = nj
 yk 2k ≤  h(
n
k = 0
 wk 2k) =h(w) 
                      (23)
かつ
n
k = nj−1
 yk 2kh(
n
k = 0
 wk 2k)=h(w 
                      (24)

のような自然数j が存在する.

不等式(22) と 不等式(24) より,

nj−1 < ns−1.     (25)

不等式(23) と補題 2.4の (ii) より,

n
k = nj
 yk 2k ≤  h(
n
k = nj+1
 wk 2k)≤ h(
n
k = nj
 wk 2k).     (26)

不等式(24)より,

n
k = nj−1
 yk 2kh(
n
k = nj
 wk 2k).     (27)

不等式(26)と不等式(27)より,

n
k = nj
 yk 2k ≤  h(
n
k = nj
 wk 2k) < 
n
k = nj−1
 yk 2k     (28)

を得る. ここで, i = n,n−1,n−2,...,0に対して,viwiの値を決めることによって vwを定義する.

まずi = n,n−1,...,njに対して

wi = wi  かつ  vi = yi     (29)

とし,次に

vnj−1 = 0 < 1 = ynj−1      (30)

かつ

wnj−1=xnj−1 + vnj−1 

と決める. vnj−1 = 0 , ynj−1=1なので 不等式 (28)より

n
k = nj−1
 vk 2k  ≤  h(
n
k = nj
 wk 2k) < 
n
k = nj−1
 vk 2k + 2nj−1.     (31)

不等式 (31) と補題2.5より,
k = nj−1n vk2kh(∑k = nj−1n wk 2k)

<
n
k = nj−1
 vk 2k+2nj−1     (32)

を得る. 次に各 t=nj−1, nj−2,...,2,1,0に対して,次の不等式 (33)が成り立つことをtを1ずつ減らしながら証明していく.

n
k = t
 vk 2k ≤  h(
n
k = t
 wk 2k) < 
n
k = t
 vk 2k + 2t.     (33)

不等式(32)より,t = nj−1の場合は不等式(33)が成り立つ. tnj−1を満たすある自然数tに対して,不等式(33)が成り立つとする.そのとき不等式 (34) または不等式(37)が成り立つ. これらの不等式を用いて(36)と(39) を証明することにする.

もし

n
k = t
 vk 2k+2t−1 ≤  h(
n
k = t
 wk 2k) < 
n
k = t
 vk 2k+2t     (34)

とすると,このとき vt−1=1 と wt−1=xt−1+ vt−1 (mod 2)とする. vt−1=1なので, 不等式 (34) より,

n
k = t−1
 vk 2k ≤  h(
n
k = t
 wk 2k) < 
n
k = t−1
 vk 2k+2t−1     (35)

を得る. vt−12t−1 + 2t−1 = 2tに注目する.

補題 2.5 と 不等式(35)より,

n
k = t−1
 vk 2k ≤  h(
n
k = t−1
 wk 2k) < 
n
k = t−1
 vk 2k+2t−1.     (36)

もし

n
k = t
 vk 2k+2t−1h(
n
k = t
 wk 2k)     (37)

ならば,そのときvt−1=0 と wt−1=xt−1+ vt−1 (mod 2)とする.
vt−1=0なので, 不等式 (37) と (33) から

n
k = t−1
 vk 2k ≤  h(
n
k = t
 wk 2k) < 
n
k = t−1
 vk 2k+2t−1     (38)

を得る. そのとき, 不等式 (38) と補題 2.5より,

n
k = t−1
 vk 2k ≤  h(
n
k = t−1
 wk 2k) < 
n
k = t−1
 vk 2k+2t−1     (39)

を得る.

この方法で不等式 (33)より,不等式 (36) または不等式(39) を得る. 不等式 (36)と不等式(39)は同じ形の不等式であることに注目する. この過程を続けることにより,

n
k = 0
 vk 2k ≤  h(
n
k = 0
 wk 2k) < 
n
k = 0
 vk 2k+20

を得る. よって

k = 0n vk 2k = h(∑k = 0n wk 2k) を得る.不等式(20), 不等式(25), 不等式(30) と等式(29)により, v < yかつw < zを得る.以上よりこの補題の(4)が成り立つ.

補題 2.7   もし xyz = 0かつyh(z)とする. このとき以下のことが成り立つ.
(i) u<xを満たすuZ ≥ 0に対してuyz ≠ 0.
(ii) v<yを満たすvZ ≥ 0 に対してxvz ≠ 0.
(iii) w<zを満たすwZ ≥ 0 に対してxyw ≠ 0.
(iv) v<y,w<zかつv= h(w)を満たすv,wZ ≥ 0 に対してxvw ≠ 0.

. この補題の( i),(ii),(iii)は定義1.1 (ニム和の定義)から直接導かれる.
( iv)を証明する.v<y,w<zを満たすwZ≥ 0に対してv= h(w)がなりたつとする.

i = n,n−1,n−2,...,j に対して wi=zi かつ wj−1<zj−1     (40)

とする. yh(z)より, h(∑k = 0n zk 2k) ≥ ∑k = 0n yk 2kを得る.故に補題2.3より

h(
n
k = j
 zk 2k) ≥  
n
k = j−1
 yk 2k     (41)

を得る. v= h(w), v < yなので, 関係 (40) から        h(∑k = jn zk 2k) = h(∑k = jn wk 2k)

≤ h(w) = v =  
n
k = 0
 vk 2k < 
n
k = 0
 yk 2k     (42)

を得る. 不等式 (41) と (42) より

n
k = j−1
 yk 2k ≤ 
n
k = 0
 vk 2k < 
n
k = 0
 yk 2k  

を得る. 故に k = n,n−1,n−2,...,j−1に対して,

vk=yk     (43)

を得る. xyz = 0 なので,

xj−1+yj−1+zj−1 = 0  (mod  2)     (44)

を得る. 関係 (40),等式 (43) 及び 等式 (44)より, xj−1+vj−1+wj−1 ≠ 0 (mod 2)を得る.故に xvw ≠ 0.

ここで,図2.1, 2.2のように苦い部分の右側にCB(f,y,z),左側に高さ1のチョコレートの直和によってできるチョコレートゲームを考える.左側の高さ1チョコレートのカットできる回数をx,右側のCB(f,y,z)の座標を合わせて,{x,y,z}でチョコレートの状態を表す.

例 2.1   直和チョコレートゲームの例
図 2.1   {4,4,9}
f(t) = ⌊ t/2 ⌋

図 2.2   {4,3,13}
f(t) = ⌊ t/4 ⌋

moveh ({x, y, z}) は座標{x, y, z}であるポジションから一回(直接)で行くことができるすべてのポジションの座標からなる集合である.

定義 2.2   x,y,zZ≥ 0に対して,
moveh({x,y,z})={{u,y,z }:u<x } ∪ {{x,v,z }:v<y } ∪ { {x,min(y, h(w) ),w }:w<z }( u,v,wZ≥ 0)

と定義する.

定義 2.3   Ak={{x,y,z}:x,y,zZ≥ 0,yh(z) , xyz=0}, Bk={{x,y,z}:x,y,zZ≥ 0,yh(z), xyz≠ 0}とおく.
補題 2.8   定義2.3の集合AkBkに対して次の(i), (ii)が成り立つ.
(i) Akからプレーを始めると,次の一手で必ずBkの場所に行く.
(ii) もしBkから始めると,Akの座標に行くことができる手が少なくとも1つある.

証明. 定義 2.2で定義される moveh ({x, y, z})は1回で 座標{x, y, z}から行けるポジションの座標を全部含んでいるので, 補題 2.7 と 補題 2.6 より それぞれ(i) と (ii) を得る.

定理 2.1   定義2.3で定義される集合 AkBkに対して, AkBkは苦いチョコレートの右側のCB(h,y,z)と左側の高さ1のチョコレートの直和ゲームのP-ポジションs の集合とN-ポジションsの集合である.
証明.もし私達が{x,y,z}∈ Akからゲームを開始したとすると,補題2.8より,先手である私達が選ぶ手は全て{p,q,r} ∈ Bkに行く.この状態で後手である相手は補題2.8により,うまく選ぶことでAkへ行くことができる.毎回のプレーによって,座標は減って行くので,有限回数内でゲームは終了する.後手である相手は常にAkへ到達することができ,最後は{0,0,0} ∈ Akへ到達し相手が勝つ.よって,Akは後手必勝(P-ポジション)の集合である.
次に,もし私達が{ x,y,z}∈ Bkからゲームを開始したとすると,補題2.8により,先手である私達は{p,q,r} ∈ Akへ行くことができる.この状態で後手である相手は,補題2.8より, 必ずBkに行く.このようにして,先手である自分は常にAkへ行くことができ,最後は{0,0,0}に到達して私達が勝つ.よって,Bkは先手必勝(N-ポジション)の集合である.

定理 2.2   hを定義 2.1の条件を満たす関数とすると,CB(h,y,z) のGrundy数は yzである.

証明. 定理 2.1より, 左の高さ1のチョコレートと右のCB(h,y,z)の直和ゲームは,座標{x,y,z}がxyz=0のときP-ポジション である. このとき,直和ゲームのGrundy数は定理 1.1の(i)から0となる.しかし 定理 1.1の(ii)によると,そのGrundy数は左の高さ1のチョコレートのGrundy数と右のCB(h,y,z)のGrundy数のニム和なので,それが0であるということは, 左の高さ1のチョコレートのGrundy数と右の CB(h,y,z)のGrundy数が等しいことになる. 左の高さ1のチョコレートのGrundy数は明らかに xとなるので, 右側の CB(h,y,z)のGrundy数はx = yzである.

定理2.2より定義2.1 の条件はチョコレートCB(h,y,z) がGrundy数 G({y,z}) = yzとなるための十分条件である.

次の小節において定義2.1の条件が,チョコレートCB(h,y,z)のGrundy数G({y,z}) = yzとなるための必要条件であることを証明する.

2.2 必要条件next