3.1 十分条件

　hを定義2.1の条件(a)を満たす関数とし，G_h({y,z})をCB(h,y,z)のGrundy数とする.定義2.1の条件(a)はCB(h,y,z)のGrundy数がG_h({y,z})=y ⊕ zを満たす必要十分条件であり，これより以前の全ての補題及び定理をh, CB(h,y,z)に用いることができる.

定義3.1の条件が，チョコレートCB(h_s,y,z)のGrundy数がG_hs({y,z})= (y ⊕ (z+s))−sとなる必要十分条件であることを証明する.

証明. 関係( 83)を仮定する．s ⊕ s = 0 < s+sなので，p < sは明らかである． p > 0のときp=∑_{k = 0}^t p_k 2^k, p_t=1かつp_k ∈ {0,1}とおく. s = ∑_{k = 0}ⁿ s_k 2^k, s_n=1かつs_k ∈ {0,1}とおく. p ⊕ s = p+sかつp_t=1なので， s_t=0となる. 0 ≤ ∑_{k = 0}^t−1 2^k < pであるので, ∑ _{k = 0}^t−1 2^k ⊕ s = ∑_{k = 0}^t−1 2^k + s.従って，i = 0,1,...,t−1に対してs_i = 0である. u = ∑_{k = t+1}ⁿ s_k 2^k−t−1 及びv=t+1としたとき，関係(84)を得る．p=0のときは，v=0かつu=sと置くと，関係(84)を得る. 次に関係( 84)を満たす自然数uと非負整数vが存在するとする.このとき関係(83)を得るのは明らかである.

証明. 補題 3.1により, s = u × 2^vかつ2^v > pを満たす自然数uと非負整数vが存在する. j ∈ Z_{≥ 0} は0 ≤ j ≤ pを満たすとすると， jは二進数として， j = ∑_{k = 0}^v−1 j_k 2^kと表される. 0 ≤ i ≤ s−1に対して0 ≤ j ⊕ i ≤ s−1が成り立つことを証明する. i ∈ Z_{≥ 0} が0 ≤ i ≤ s−1を満たすとすると， u^′ < uかつi = u^′ × 2^v + ∑_{k = 0}^v−1 i_k 2^k (i_k ∈ {0,1})を満たすu^′ ∈ Z_{≥ 0}が存在する. 従って，

0 ≤ j ⊕ i = u′ × 2v +

v−1 ∑ k = 0

(jk ⊕ ik) 2k < u × 2v = s.     (86)

0 ≤ i, i^′ ≤ s−1においてj ⊕ i ≠ j ⊕ i^′ (i ≠ i^′)なので, 不等式(86)は関係(85)を示す.

証明. mex({x_k:k=1,2,...,n} ∪ {0,1,2,...,s−1}) = xであると仮定する. 補題1.1より, x ∉ {x_k:k=1,2,...,n} ∪ {0,1,2,...,s−1}であり，したがってx−s ∉ {x_k−s:k=1,2,...,n}である． u<x−sをみたすu ∈ Z_{≥ 0}に対して，u+s<xであり 補題1.1よりu+s ∈ {x_k:k=1,2,...,n} ∪ {0,1,2,...,s−1}が示される．したがって， ある自然数 kに対してu+s=x_kとなり，u=x_k−sである. 補題 1.1より, mex({x_k−s:k=1,2,...,n} ) = x−sを得る.
逆に mex({x_k−s:k=1,2,...,n} ) = x−sと仮定する. 補題1.1により，k = 0,1,...,nに対してx−s ≠ x_k −sで，したがってk = 0,1,...,nに対してx ≠ x_kとなる. x > v ≥ sを満たすv ∈ Z_{≥ 0}に対して，v = u +sかつx−s > u ≥ 0を満たすuが存在するので，補題1.1より, u = x_k −sを満たすkが存在し， したがってv = x_kを得る. したがって補題 1.1よりmex({x_k:k=1,2,...,n} ∪ {0,1,2,...,s−1}) = xが示される.

証明. 定理 2.2及びGrundy数の定義より,

y ⊕ (z+s) = Gh({y,z+s})                 =mex({Gh({v,z+s}):v<y}      ⋃ {Gh({ min(y,h(w)),w}):w < z+s})     =mex({Gh({v,z+s}):v<y}      ⋃ {Gh({ min(y,h(w)),w}):w < s}     ⋃ {Gh({ min(y,h(w)),w}):s ≤ w < z+s}) .     (89)

w < sのとき, h(w) ≤ h(s)とり， したがって min( y,h(w)) = min( min(y,h(s)),h(w)). min(y,h(s)) ∈ Z_{≥ 0} かつ min(y,h(s)) ≤ h(s)だから, 補題 2.10, 等式(87)と 補題3.2によって { G_h({ min(y,h(w)),w}):w < s} = {G_h({ min(min(y,h(s)),h(w)),w}):w < s}
= {min(y,h(s)) ⊕ w:w<s} ={0,1,2,...,s−1}となる. したがって, 定理2.2より,

(89) =mex({v⊕ (z+s):v<y } ⋃ {0,1,2,...,s−1}       ⋃ { min(y,h(w)) ⊕ w:s ≤ w < z+s }).      (90)

等式(89)及び等式(90)により等式(88)は示される. したがって, 補題1.2より, y ⊕ (z+s) ≥ sを得る.

証明. 関係( 91)及び補題3.4より,y ≤ h(z+s)を満たすy,z ∈ Z_{≥ 0}に対して G_h({y,z+s})

= y ⊕ (z+s) =  mex({v⊕ (z+s):v<y } ⋃ {0,1,2,...,s−1}          ⋃ { min(y,h(w)) ⊕ w:s ≤ w < z+s })                 (93)

= y ⊕ (z+s) =  mex({v⊕ (z+s):v<y } ⋃ {0,1,2,...,s−1}          ⋃ { min(y,h(w′+s)) ⊕ (w′+s):         0 ≤ w′ < z })          (94)

を得る. v < y ≤ h(z+s)だから, 補題3.4より0 ≤ v < yに対して，

v⊕ (z+s)≥ s.     (95)

min(y,h(w^′+s)) ≤ h(w^′+s)だから, 補題3.4より0 ≤ w^′ < zに対して

min(y,h(w′+s)) ⊕ (w′+s) ≥ s.     (96)

補題3.3, (95)の不等式, (96)の不等式及び等式 (94)により(92)は示される.

証明. y,z ∈ Z_≥0がy ≤ h_s(z)を満たすとする．数学的帰納法によって証明を行う. v ≤ y, w< zもしくはv < y, w ≤ zを満たすv,w ∈ Z_{≥ 0}に対してG_hs({v,w})= (v ⊕ (w+s))−sであると仮定する.

Ghs({y,z})=mex({Ghs({v,z}):v<y} ⋃ {Ghs({ min(y,hs(w)),w}):w < z})         =mex({(v ⊕ (z+s))−s :v<y} ⋃ { (min(y,h(w+s)) ⊕ (w+s))−s :w< z })       =mex({(v ⊕ (z+s))−s :v<y} ⋃ { (min(y,h(w+s)) ⊕ (w+s))−s :s ≤ w+s < z+s})       =mex({(v ⊕ (z+s))−s :v<y} ⋃ { (min(y,h(w′)) ⊕ w′)−s :s ≤ w′ < z+s}) .         (98)

補題3.5より, (98) = (y ⊕ (z+s))−s ,よって証明が終わる.