2.1 十分条件

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

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

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

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

等式 (3)が成立しないとする． そのとき，ある u ∈ Z_{≥ 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.1の条件の対偶を証明する． 等式( 3)が成立しないとする． 自然数 iに対して，

⌊

2⌊ log2z⌋−1 2i−1

⌋  <    ⌊

2⌊ log2z′⌋−1 2i−1

⌋.     (6)

z = 2^n+m , z^′=2^n′+m′とおく．ここで，n, n^′ ∈ Z_≥0, 0 ≤ m,m^′ < 1である． そのとき不等式 (6)より，

⌊ 2n−i  ⌋ < ⌊ 2n′−i  ⌋.     (7)

不等式(7)より，

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

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

⌊

z 2i

⌋ =  ⌊ 2n+m−i  ⌋ <  2n′−i ≤  ⌊ 2n′+m′−i  ⌋ = ⌊

z′ 2i

⌋.

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

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

. h(∑_{k = 0}ⁿ z_k 2^k) = ∑_{k = 0}ⁿ u_k 2^kとおく. ここで u_k ∈ {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に対して z_k^′ = 0とおく． 不等式( 11), 定義2.1 ,注意 2.1より，k=0,...,i−2 に対して y_k^′ が存在して，

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.

となる．

. ( i)を証明する．h(∑_{k = 0}ⁿ p_k 2^k)= ∑_{k = 0}ⁿ r_k 2^kとおく．ここでr_k ∈ {0,1}とする． そのとき，注意 2.1より, k=0,1,2,...,i−2に対してr_k^′が存在して， h(∑_{k = i}ⁿ p_k 2^k + ∑_{k = 0}ⁱ⁻¹ 0 × 2^k) = ∑_{k = i−1}ⁿ r_k 2^k+∑_{k = 0}ⁱ⁻² r_k^′ 2^k. そのとき, 不等式 (12)より,

n ∑ k = i−1

qk 2k >

n ∑ k = i−1

rk 2k+

i−2 ∑ k = 0

rk′ 2k

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

qn > rn.     (13)

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

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

そのとき，不等式(13)または関係(14)より, ∑ _{k = i−1}ⁿ q_k 2^k > ∑_{k = i−1}ⁿ r_k 2^k+∑_{k = 0}ⁱ⁻² r_k 2^k

=

n ∑ k = 0

rk 2k=h(

n ∑ k = 0

pk 2k).

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

. ∑ _{k = i−1}ⁿ⁺¹ q_k^′ 2^k = ∑_{k = i−1}ⁿ q_k 2^k+2ⁱ⁻¹とp_n+1=0とおく.そのとき, 不等式(15)より, h(∑_{k = i}ⁿ⁺¹ p_k 2^k) < ∑_{k = i−1}ⁿ⁺¹ q_k^′ 2^kを得る． 補題 2.4の(i)により h(∑_{k = i−1}ⁿ p_k 2^k) ≤ h(∑_{k = 0}ⁿ⁺¹ p_k 2^k) < ∑_{k = i−1}ⁿ⁺¹ q_k^′ 2^k =∑_{k = i−1}ⁿ q_k 2^k+2ⁱ⁻¹となり，この補題は示された．

. x= ∑_{k = 0}ⁿ x_k 2^k, y= ∑_{k = 0}ⁿ y_k 2^k, z= ∑_{k = 0}ⁿ z_k 2^kとする．n=0ならばこの補題は自明であるからn ≥ 1と仮定する．

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

xn−s−1 + yn−s−1 + zn−s−1 ≠ 0  (mod  2)     (17)

となり，i = n,n−1,...,n−sに対してx_i + y_i + z_i = 0 (mod 2)が成り立つとする．
Case (i) x_n−s−1=1となる場合． このとき， u = ∑_i=1ⁿu_i2ⁱを次のように決める．まずi=n,n−1,..., n−s に対してu_i=x_iとし，u_n−s−1=0<x_n−s−1として，i=n−s−2,n−s−3,...,0に対してu_i=y_i+z_i ( mod 2 )と決める． このとき u ⊕ y ⊕ z = 0かつu<xとなって(1)が成り立つ.
Case (ii) y_n−s−1=1となる場合は(i)で使った方法と同じようにして, v<yとなるようなv ∈ Z_{≥ 0}があってx ⊕ v ⊕ z = 0となり，(2)が成り立つ.
Case (iii)

zn−s−1 =1     (18)

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

wi = zi     (19)

として，各i=n−s−1,...,0に対して，w_i = x_i + y_i (mod 2) とする． 不等式( 17)と等式(18)より， w_n−s−1 =x_n−s−1+y_n−s−1 = 0 (mod 2)を得る． 故に

wn−s−1=0 < 1 = zn−s−1.     (20)

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

y > h(w)     (21)

となる場合を考える． 不等式( 16)より ∑_{k = 0}ⁿ y_k 2^k ≤ h(∑_{k = 0}ⁿ z_k 2^k)となる．故に 補題 2.3 と 等式(19)より

n ∑ k = n−s−1

yk 2k ≤  h(

n ∑ k = n−s

zk 2k)=h(

n ∑ k = n−s

wk 2k) ≤ h(w).     (22)

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

n ∑ k = n−j  yk 2k ≤  h( n ∑ k = 0  wk 2k) =h(w)                        (23) かつ n ∑ k = n−j−1  yk 2k >  h( n ∑ k = 0  wk 2k)=h(w)                         (24)

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

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

n−j−1 < n−s−1.     (25)

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

n ∑ k = n−j

yk 2k ≤  h(

n ∑ k = n−j+1

wk 2k)≤ h(

n ∑ k = n−j

wk 2k).     (26)

不等式(24)より,

n ∑ k = n−j−1

yk 2k >  h(

n ∑ k = n−j

wk 2k).     (27)

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

n ∑ k = n−j

yk 2k ≤  h(

n ∑ k = n−j

wk 2k) <

n ∑ k = n−j−1

yk 2k     (28)

を得る． ここで， i = n,n−1,n−2,...,0に対して，v_iとw_i^′の値を決めることによって vとw^′を定義する．

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

wi′ = wi  かつ  vi = yi     (29)

とし，次に

vn−j−1 = 0 < 1 = yn−j−1      (30)

かつ

wn−j−1′=xn−j−1 + vn−j−1

と決める． v_n−j−1 = 0 , y_n−j−1=1なので 不等式 (28)より

n ∑ k = n−j−1

vk 2k  ≤  h(

n ∑ k = n−j

wk′ 2k) <

n ∑ k = n−j−1

vk 2k + 2n−j−1.     (31)

不等式 (31) と補題2.5より，
∑ _{k = n−j−1}ⁿ v_k2^k ≤ h(∑_{k = n−j−1}ⁿ w_k^′ 2^k)

<

n ∑ k = n−j−1

vk 2k+2n−j−1     (32)

を得る． 次に各 t=n−j−1, n−j−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 = n−j−1の場合は不等式(33)が成り立つ． t ≤ n−j−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)

とすると,このとき v_t−1=1 と w_t−1^′=x_t−1+ v_t−1 (mod 2)とする． v_t−1=1なので, 不等式 (34) より,

n ∑ k = t−1

vk 2k ≤  h(

n ∑ k = t

wk′ 2k) <

n ∑ k = t−1

vk 2k+2t−1     (35)

を得る． v_t−12^t−1 + 2^t−1 = 2^tに注目する．

補題 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−1 >  h(

n ∑ k = t

wk′ 2k)     (37)

ならば，そのときv_t−1=0 と w_t−1^′=x_t−1+ v_t−1 (mod 2)とする．
v_t−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 = 0}ⁿ v_k 2^k = h(∑_{k = 0}ⁿ w_k^′ 2^k) を得る．不等式(20), 不等式(25), 不等式(30) と等式(29)により, v < yかつw^′ < zを得る．以上よりこの補題の(4)が成り立つ．

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

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

とする． y ≤ h(z)より, h(∑_{k = 0}ⁿ z_k 2^k) ≥ ∑_{k = 0}ⁿ y_k 2^kを得る．故に補題2.3より

h(

n ∑ k = j

zk 2k) ≥

n ∑ k = j−1

yk 2k     (41)

を得る． v= h(w), v < yなので， 関係 (40) から        h(∑_{k = j}ⁿ z_k 2^k) = h(∑_{k = j}ⁿ w_k 2^k)

≤ 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)

を得る． x ⊕ y ⊕ z = 0 なので，

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

を得る． 関係 (40)，等式 (43) 及び 等式 (44)より， x_j−1+v_j−1+w_j−1 ≠ 0 (mod 2)を得る．故に x ⊕ v ⊕ w ≠ 0.

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

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

と定義する．

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

証明.もし私達が{x,y,z}∈ A_kからゲームを開始したとすると，補題2.8より，先手である私達が選ぶ手は全て{p,q,r} ∈ B_kに行く．この状態で後手である相手は補題2.8により，うまく選ぶことでA_kへ行くことができる．毎回のプレーによって，座標は減って行くので，有限回数内でゲームは終了する．後手である相手は常にA_kへ到達することができ，最後は{0,0,0} ∈ A_kへ到達し相手が勝つ．よって，A_kは後手必勝(P-ポジション)の集合である．
次に，もし私達が{ x,y,z}∈ B_kからゲームを開始したとすると，補題2.8により，先手である私達は{p,q,r} ∈ A_kへ行くことができる．この状態で後手である相手は，補題2.8より， 必ずB_kに行く．このようにして，先手である自分は常にA_kへ行くことができ，最後は{0,0,0}に到達して私達が勝つ．よって，B_kは先手必勝(N-ポジション)の集合である．

証明. 定理 2.1より, 左の高さ1のチョコレートと右のCB(h,y,z)の直和ゲームは，座標{x,y,z}がx⊕ y⊕ z=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 = y⊕ zである．

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

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