2.2  必要条件

　この小節ではGrundy数が y ⊕ zと等しくなるようなチョコレートの必要条件について述べる．

この小節を通して，関数fは定義 2.4の(a)を満たすことを仮定する．そして，この関数が 定義 2.1の(a)を満たすことを証明する．そのために以下の補題を使う．

証明. y=f(z)なので，w ≤ zを満たすwに対してf(w) ≤ y < y^′となる．よって

move_f({y^′,z+1})= {{v,z+1 }:v<y^′ } ∪ { {min(y^′, f(w)),w }:w<z+1 } = {{v,z+1 }:v<y^′ } ∪ { {f(w),w }:w<z+1 } ={{ v,z+1}: y ≤ v < y^′ } ∪ {{v,z+1 }:v<y } ∪ { {f(w),w }:w<z+1 }

={{v,z+1}: y ≤ v < y^′ } ∪ {{v,z+1 }:v<y } ∪ { {min(y, f(w)),w }:w<z+1 } ={{ v,z+1}: y ≤ v < y^′ } ∪ move_f({y,z+1})(ここでv,w ∈ Z_{≥ 0}).

よって，

G({y′,z+1}) = mex({G({v,z+1}):y ≤ v < y′ }  ⋃         {G({a,b}):{a,b} ∈ movef({y,z+1})}           ≥ G({y,z+1}).       (45)

{y,z+1} ∈ move_f({y^′,z+1})なのでG({y^′,z+1}) ≠ G({y,z+1}). よって不等式( 45)によってG({y,z+1}) < G({y^′,z+1})が証明される．

証明. w ∈ Z_≥0はw< zを満たすとして,

n = ⌊ log2 max(y,z) ⌋ +1     (46)

とおく．

そのとき等式(46)によりy ⊕ w < y ⊕ (z+2ⁿ) = G({y,z+2ⁿ})となる． Grundy数の定義より，{ a,b} ∈ move_f({y,z+2ⁿ}) , G({a,b})=y ⊕ wとなるa,b ∈ Z_≥0 が存在している．
move_fの定義より，以下の等式 ( 47) または等式(48)のどちらかが成り立つ．

G({ min(y,f(w′)), w′ }) = y ⊕ w.     (47)

ここで，w^′ ∈ Z_≥0かつw^′ < z+2ⁿである．

y′ ⊕( z+2n) = G({y′, z+2n}) = y ⊕ w.     (48)

ここで，y^′ ∈ Z_≥0かつy^′ < yである．
等式 (48) は等式(46)に矛盾しており，故に 等式 (47)が正しいことになる． もし

w′ ≥ z     (49)

ならばそのとき f(w^′) ≥ f(z) ≥ y. 故に

G({ min(y,f(w′)), w′ }) =  G({y,w′ }) = y ⊕ w′.     (50)

等式(47), 等式(50)より

y ⊕ w = y ⊕ w′     (51)

を得る． w^′ < wなので(51) は矛盾している．よって，不等式(49)は成立しないので， w^′ < zとなる．故に 等式 (47)により{y ⊕ w:w < z} ⊂ {G({ min(y,f(w)),w}):w<z}が示される． { y ⊕ w:w < z}の要素の数は {G({ min(y,f(w)),w}):w<z}の要素の数と同じなので{G({ min(y,f(w)),w}):w<z} = {y ⊕ w:w < z}を得る．

証明. 0 ≤ t < 2ⁱに対して

f(a) = c × 2i+1 + t     (52)

とおく．

f(a+1) ≥ c × 2i+1 + 2i     (53)

と仮定して，このことから矛盾がでることを示す．(背理法で証明する．)
Case (i) もし d_i = 1ならば

G({c × 2i+1+2i,a+1})           = (c × 2i+1 + 2i) ⊕ (d × 2i+1 + di 2i + e)           = (c ⊕ d) 2i+1 + e < (c ⊕ d) 2i+1 + di 2i + (t⊕ e)           = G({c × 2i+1 + t, a +1}).     (54)

である． 等式( 52),不老式 (53) 及び 補題 2.9により G({c × 2ⁱ⁺¹ + t, a +1})< G({c × 2ⁱ⁺¹+2ⁱ,a+1})を得るが，これは 等式( 54)と矛盾する．
Case (ii) もしd_i = 0ならば G({c × 2ⁱ⁺¹+2ⁱ,a+1}) = (c × 2ⁱ⁺¹ + 2ⁱ) ⊕ (d × 2ⁱ⁺¹ + e)
= (c ⊕ d) 2ⁱ⁺¹ + 2ⁱ + e > (c ⊕ d) 2ⁱ⁺¹ + 2ⁱ .
ここで， d_i2ⁱ + e > 0 , d_i = 0なのでe > 0に注意して欲しい． Grundy数の定義より

(c ⊕ d) 2i+1 + 2i ∈ {G({p,q}):{p,q}           ∈ movef({c × 2i+1+2i,a+1})}.     (55)

{G({p,q}):{p,q} ∈ move_f({c × 2ⁱ⁺¹+2ⁱ,a+1})}

= {G({v,d × 2i+1+e}):v = 0,1,2,...,c × 2i+1+2i−1}         ⋃ {G({ min(c × 2i+1+2i,f(w)),w }):          w = 0,1,2,...,d × 2i+1+e−1 }.       (56)

ここでa=d × 2ⁱ⁺¹+e−1に注意して欲しい．

w ≤ aに対して, f(w) ≤ f(a) = c× 2ⁱ⁺¹ + tであるから，

(56) =          {G({v,d × 2i+1+e}):          v = 0,1,2,...,c × 2i+1+2i−1}         ⋃ {G({ min(c × 2i+1+t,f(w)),w }):           w = 0,1,2,...,d × 2i+1+e−1 }.          (57)

c × 2ⁱ⁺¹+t=f(a) ≤ f(a+1)=f(d × 2ⁱ⁺¹+e)なので，補題 2.10により{G({ min(c × 2ⁱ⁺¹+t,f(w)),w }):w = 0,1,2,...,d × 2ⁱ⁺¹+e−1 } = {(c × 2ⁱ⁺¹+t) ⊕ w: w = 0,1,2,...,d × 2ⁱ⁺¹+e−1 }となる．従って定義2.4 より，

(57) =           {v ⊕ (d × 2i+1+e): v = 0,1,2,...,c × 2i+1+2i−1}         ⋃ {(c × 2i+1+t) ⊕ w:           w = 0,1,2,...,d × 2i+1+e−1 }

= {(c × 2i+1+k)⊕(d × 2i+1+e):          k = 0,1,2,...,2i−1}         (58)     ⋃ {k ⊕ (d × 2i+1+e):          k = 0,1,2,...,c × 2i+1−1}       (59)     ⋃ { (c × 2i+1+t) ⊕ (d × 2i+1+k):          k = 0,1,2,...,e−1}       (60)     ⋃ {  (c × 2i+1+t) ⊕ k:          k = 0,1,2,...,d × 2i+1−1 }.      (61)

このとき以下の(i), (ii), (iii), (iv)が成り立つ．
( i) 集合(58)に属する全ての数は，(c⊕ d)2ⁱ⁺¹ + (k ⊕ e)の形の数であり， ( c ⊕ d) 2ⁱ⁺¹ + 2ⁱを含まない．ここで，k,e < 2ⁱに注意されたい．
( ii) 集合(59) の数の 2ⁱ⁺¹の係数はc⊕ dではない，故にこの集合は(c ⊕ d) 2ⁱ⁺¹ + 2ⁱを含まない．
( iii) 集合(60) に含まれるすべての数は (c⊕ d)2ⁱ⁺¹ + (t ⊕ k)の形の数になっている． 故にこの集合は( c ⊕ d) 2ⁱ⁺¹ + 2ⁱを含んでいない．
k ≤ e−1 < 2ⁱと t < 2ⁱに注目する．
( iv) 集合(61)の2ⁱ⁺¹ の係数はc⊕ dではない．故にこの集合は(c ⊕ d) 2ⁱ⁺¹ + 2ⁱを含んでいない．
( i), (ii), (iii) , (iv) は関係 (55)に矛盾している．よって不等式(53) は成立しないことが示された．このことで定理の証明が終る．

証明. 背理法で証明する． fが定義 2.1の条件を満たさないと仮定すると， そのとき z < z^′を満たすz,z^′ ∈ Z_{≥ 0}と自然数jが存在して，

⌊

z 2j

⌋ = ⌊

z′ 2j

⌋     (62)

かつ

⌊

f(z) 2j−1

⌋ < ⌊

f(z′) 2j−1

⌋.     (63)

等式 (62)より，k =0,1,2,...,nに対してz_k, z_k^′ ∈ Z_{≥ 0}が存在して， z=∑_{k = 0}ⁿ z_k 2^kと z^′ = ∑_{k = j}ⁿ z_k 2^k+∑_{k = 0}^j−1 z_k^′ 2^kが成り立つ． 不等式 (63)により，自然数 i ≥ j−1とk =0,1,2,...,nに対してy_k, y_k^′ ∈ Z_{≥ 0} が存在して， y_i = 0 < 1 = y_i^′,

f(

n ∑ k = 0

zk 2k)=

n ∑ k = i+1

yk 2k  + yi × 2i +

i−1 ∑ k = 0

yk 2k     (64)

かつ

f(

n ∑ k = j

zk 2k+

j−1 ∑ k = 0

zk′ 2k) =

n ∑ k = i+1

yk 2k+ yi′ × 2i +

i−1 ∑ k = 0

yk′ 2k     (65)

が成り立つ．

c =∑_{k = i+1}ⁿ y_k 2^k−(i+1) とする. そのとき c × 2ⁱ⁺¹ = ∑_{k = i+1}ⁿ y_k 2^kとなる．

等式(64)と等式 (65)から

f(

n ∑ k = 0

zk 2k)=  c × 2i+1 + 0 × 2i +

i−1 ∑ k = 0

yk 2k     (66)

と

f(

n ∑ k = j

zk 2k+

j−1 ∑ k = 0

zk′ 2k) = c × 2i+1+ 2i +

i−1 ∑ k = 0

yk′ 2k     (67)

を得る．

a = max({z: f(z) < c × 2i+1 + 2i})     (68)

と

b =  min({z: f(z) ≥  c × 2i+1 + 2i})     (69)

とする． そのとき，( 68)と(69)から直接b = a+1が出る．

d =∑_{k = i+1}ⁿ z_k 2^k−(i+1) とする. そのとき, d × 2ⁱ⁺¹ = ∑_{k = i+1}ⁿ z_k 2^kとなる． 等式( 66)により， f(d × 2ⁱ⁺¹) ≤ f(∑_{k = 0}ⁿ z_k 2^k) <c × 2ⁱ⁺¹+2ⁱとなり， 等式( 68)を使うと

a ≥

n ∑ k = 0

zk 2k ≥ d × 2i+1     (70)

を得る． i+1 ≥ jより, ( d+1) × 2ⁱ⁺¹ =∑_{k = i+1}ⁿ z_k 2^k+2ⁱ⁺¹

>

n ∑ k = j

zk 2k+

j−1 ∑ k = 0

zk′ 2k     (71)

を得る. 等式( 67)と等式 (69)から

n ∑ k = j

zk 2k+

j−1 ∑ k = 0

zk′ 2k ≥ b.     (72)

不等式(71)と不等式(72)から

(d+1) × 2i+1 > b = a+1     (73)

を得る． 不等式 (70)から

a+1 >d × 2i+1     (74)

を得る． 不等式( 73)と不等式(74)により， ( d+1) × 2ⁱ⁺¹ > b = a+1 > d × 2ⁱ⁺¹となり， e < 2ⁱ，0<d_i 2ⁱ + eを満たすd_i と e が存在して

a+1 = d × 2i+1 + di2i + e.     (75)

となる． 等式( 66)と不等式(70)により,

f(a) ≥ f(

n ∑ k = 0

zk 2k)  ≥ c × 2i+1     (76)

を得る． 等式 (68)から

f(a) < c × 2i+1 + 2i     (77)

と

f(a+1) ≥ c × 2i+1 + 2i     (78)

が導かれる．

等式(75)，不等式(76), 不等式(77) と不等式 (78)は補題 2.11の結果と矛盾する ．故に f は定義2.1の条件を満たす．

定理2.3より，不等式2.1 はGrundy数G({y,z})=y ⊕ zとなるCB(f,y,z) の必要条件である．