3.1 十分条件

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

定義 3.1   関数hsを以下の様に定義する.
si = 0,1,2,...,h(s)に対して,
i ⊕ s = i + s 
となる自然数とする.
この
sを固定しておいて,各zZ≥0に対してhs(z) = h(z+s) とする.

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

補題 3.1   pZ≥ 0及びsを自然数とする.このとき,
i = 0,1,...,p  において  i ⊕ s = i+s      (83)
となる必要十分条件は以下の条件を満たす自然数u及び非負整数vが存在することである.
s = u × 2v  かつ  2v > p.     (84)

証明. 関係( 83)を仮定する.ss = 0 < s+sなので,p < sは明らかである. p > 0のときp=∑k = 0t pk 2k, pt=1かつpk ∈ {0,1}とおく. s = ∑k = 0n sk 2k, sn=1かつsk ∈ {0,1}とおく. ps = p+sかつpt=1なので, st=0となる. 0 ≤ ∑k = 0t−1 2k < pであるので, ∑ k = 0t−1 2ks = ∑k = 0t−1 2k + s.従って,i = 0,1,...,t−1に対してsi = 0である. u = ∑k = t+1n sk 2kt−1 及びv=t+1としたとき,関係(84)を得る.p=0のときは,v=0かつu=sと置くと,関係(84)を得る. 次に関係( 84)を満たす自然数uと非負整数vが存在するとする.このとき関係(83)を得るのは明らかである.

補題 3.2   pZ≥ 0とし,si = 0,1,...,pに対して,is = i+sを満たす自然数とする. jZ≥ 00 ≤ jpを満たすとする.このとき,
     
  集合 {j ⊕ i:i=0,1,2,...,s−1 } は集合  
  {0,1,2,...,s−1}と等しい.      (85)

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

0 ≤ j ⊕ i = u × 2v + 
v−1
k = 0
 (jk ⊕ ik) 2k < u × 2v = s.     (86)

0 ≤ i, is−1においてjiji (ii)なので, 不等式(86)は関係(85)を示す.

補題 3.3   sを自然数とし, xZ≥ 0及びk=1,2,...,nに対してxkZ≥ 0とおく. k=1,2,...,nに対してx,xksと仮定する.このとき, mex({xk:k=1,2,...,n} ∪ {0,1,2,...,s−1}) = xとなる必要十分条件は mex({xks:k=1,2,...,n} ) = xsが成り立つことである.

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

補題 3.4   s
i = 0,1,2,...,h(s) に対して  i ⊕ s = i + s     (87)
を満たす自然数とする.このとき,yh(z+s)となる全てのy,zZ≥ 0に対して
     
  y ⊕ (z+s) = Gh({y,z+s})                     
mex({v⊕ (z+s):v<y } ⋃ {0,1,2,...,s−1}      
⋃ {min(y,h(w)) ⊕ w:s ≤ w < z+s}).         (88)
を得る. 特に y ⊕ (z+s) ≥ s.

証明. 定理 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によって { Gh({ min(y,h(w)),w}):w < s} = {Gh({ 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を得る.

補題 3.5   s
i = 0,1,2,...,h(s) に対して  i ⊕ s = i + s      (91)
を満たす自然数とする. yh(z+s)を満たすいずれのy,zZ≥ 0に対して,
     
(y ⊕ (z+s))−s  =          
mex({(v⊕ (z+s))−s:v<y }⋃ {( min(y,h(w)) ⊕ w)−s:s ≤ w < z+s })           (92)
を得る.

証明. 関係( 91)及び補題3.4より,yh(z+s)を満たすy,zZ≥ 0に対して Gh({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 < yh(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)は示される.

定理 3.1   s
i = 0,1,2,...,h(s) に対して i ⊕ s = i + s       (97)
となる自然数とし, zZ≥0に対して,hs(z) = h(z+s)とする. CB(hs,y,z)のGrundy数をGhs({y,z})とおく. このときyhs(z)を満たすy,zZ≥0に対してGhs({y,z})= (y ⊕ (z+s))−sとなる.

証明. y,zZ≥0yhs(z)を満たすとする.数学的帰納法によって証明を行う. vy, w< zもしくはv < y, wzを満たすv,wZ≥ 0に対してGhs({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 :wz })      
=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 ,よって証明が終わる.

3.2 必要条件 next