必要条件

3.2 必要条件

　この小節では,Grundy数が( y ⊕ (z+s))−sとなるチョコレートの必要条件の研究を行う.

定義 3.2 自然数の定数sと, gを以下の条件を満たす関数であるとする:
(i) g(t)∈ Z_≥0 for t ∈ Z_≥0.
(ii) gは単調増加．
(iii) CB(g,y,z)のGrundy数はG_g({y,z})= (y ⊕ (z+s))−s.

定義3.2の関数gに対して，関数 hが存在して， z ∈ Z_≥0に対してg(z) = h(z+s)であって，

i = 0,1,2,...,h(s) に対して i ⊕ s = i + s,

かつCB(h,y,z)のGrundy数がG_h({y,z})= (y ⊕ z)となることを示す.

補題 3.6 sを自然数とし，関数hが定義3.2の条件を満たすとする. このとき i=0,1,2,...,g(0)に対して，i ⊕ s = i + sとなる.

証明. 最初に， i = 0,1,2,...,g(0)に対して

G_g({i,0})=i (99)

であることを数学的帰納法を用いて証明を行う. Grundy数の定義より, G_g({0,0})=0. k = 0,1,2,...i−1に対してG_g({k,0})=kかつ i ≤ g(0)であると仮定する. Grundy数の定義より, G_g({i,0})=mex({G_g({k,0}):k=0,1,2,...,i−1} =mex({0,1,2,...,i−1})=i. 定義 3.2の条件より, G_g({i,0})= (i ⊕ s)−sとなり，したがって等式(99)により ( i ⊕ s)−s = iが示される．

定理 3.2 sを自然数とし, gを定義3.2の条件を満たす関数とする. このとき，関数g_−sを z ≥ sに対してg_−s(z)=g(z−s), 0 ≤ z < sに対してg_−s(z)=g(0)と定義する. G_{g_−s}({y,z})を CB(g_−s,y,z)のGrundy数とする. このとき, y ≤ g_−s(z)を満たすy,z ∈ Z_{≥ 0}に対してG_{g_−s}({y,z})= y ⊕ zとなる.

証明. Case (1) g_−sの定義により, z ≤ sに対してg_−s(z)=g(0)となり，したがって関数g_−sはz ≤ sに対して定数値関数であるから，定義2.1の条件を満たす. これゆえ y ≤ g_−s(z)かつz ≤ sとなるy,z ∈ Z_{≥ 0}に対してG_{g_−s}({y,z})= y ⊕ zとなる.
Case (2) 次にy ≤ g_−s(z+s)に対してG_{g_−s}({y,z+s})= y ⊕ (z+s)となることを証明する. 数学的帰納法で証明を行い, v ≤ y, w< z+sもしくはv < y, w ≤ z+sとなるv,w ∈ Z_{≥ 0}においてG_{g_−s}({v,w})= v ⊕ wであると仮定する. 補題 3.6からi=0,1,2,...,g(0)に対して，i ⊕ s = i + sとなり， p=g(0),j = min(y,g(0))と考えて補題3.2を使うと，次の関係( 100)を得る.

集合 { min( y,g(0)) ⊕ w:w < s} は集合
{0,1,2,...,s−1}と等しい.			(100)

定義 3.2より,

(y ⊕ (z+s))−s=G_g({y,z})=mex({G_g({v,z}):v<y} ⋃ {G_g({ min(y,g(w)),w}):w < z})
=mex({(v ⊕ (z+s))−s:v<y} ⋃ { (min(y,g(w)) ⊕ (w+s))−s : w < z})
=mex({(v ⊕ (z+s))−s:v<y} ⋃ { (min(y,g_−s(w+s)) ⊕ (w+s))−s :s ≤ w+s < z+s}).			(101)

式101において，mexの中に入っている集合について考えていく．

		v<y に対して (v ⊕ (z+s))−s = G_g({v,z}) ≥ 0
		かつ
		s ≤ w+s < z+s に対して ,
		(min(y,g_−s(w+s)) ⊕ (w+s))−s
		= G_g({ min(y,g(w)),w}) ≥ 0

したがって

		v<y に対して (v ⊕ (z+s)) ≥ s	(102)
		かつ
		s ≤ w+s < z+s に対して
		(min(y,g_−s(w+s)) ⊕ (w+s)) ≥ s.	(103)

帰納法の仮定により，

		G_{g_−s}({y,z+s}) =mex({G_{g_−s}({v,z+s}):v<y}
		⋃ {G_{g_−s}({ min(y,g_−s(w)),w}):w < s}
		⋃ {G_{g_−s}({ min(y,g_−s(w)),w}):s ≤ w < z+s})

		=mex({v ⊕ (z+s):v<y} ⋃ { min(y,g_−s(w)) ⊕ w:w < s}
		⋃ { min(y,g_−s(w)) ⊕ w :s ≤ w < z+s}).	(104)

0 ≤ w < sに対してg_−s(w)=g(0)であるので, 関係(100)により{ min(y,g_−s(w)) ⊕ w:w < s} = { min(y,g(0)) ⊕ w:w < s}={0,1,2,...,s−1}は示される. 今から補題 3.3を使うにあたって，この補題におけるxに対応するものとして y ⊕ (z+s)，{x_k, k = 1,2,...,n}に対応するものとして， { v ⊕ (z+s):v<y} ∪ { min(y,g_−s(w)) ⊕ w :s ≤ w < z+s}とすると，等式(101), (102)の不等式, (103)の不等式, 等式(104) によって補題3.3を使うことができ， G_{g_−s}({y,z+s})=y ⊕ (z+s)は示される.

定理3.1及び定理3.2により以下の命題(i)及び(ii)はそれぞれ証明される.
( i) hをチョコレートCB(h,y,z)のGrundy数がG_h({y,z}) = y ⊕ zとなる関数とする.このときsが条件(97)を満たし, h_s(z)=h(z+s)となる場合においてチョコレートCB(h_s,y,z)のGrundy数G_{h_s}({y,z}) = (y ⊕ (z+s))−sとなる.
( ii) gをチョコレートCB(g,y,z)のGrundy数がG_g({y,z}) = (y ⊕ (z+s))−sとなる関数とする. このときg_−s(z)=h(z−s)とおくと，チョコレートCB(g_−s,y,z)のGrundy数がG_{g_−s}({y,z}) = y ⊕ zとなる. ここでg=(g_−s)_sである.
故に, チョコレートCB(h,y,z)のGrundy数がG_{h_s}({y,z}) = (y ⊕ (z+s))−sとなる必要十分条件を得た.

次に関数h(z)=⌊ z/2k⌋における条件の例を示す. この様に, この関数において条件は非常に単純である.

系 3.1 自然数の定数kに対してh(z)=⌊ z/2k⌋とする. このとき

m = 0, 1, 2,...,2k−1 となる m,v ∈ Z_≥ 0 に対して s = m2^v (105)

となることは， CB(h_s,y,z)のGrundy数が(y⊕ (z+s)) −sに等しくなるための必要十分条件である.　ただし，h_s(z) = ⌊ z+s/2k⌋とする．

証明. 補題2.1より, 関数hは定義2.1の条件を満たす. 補題 3.1より,

i = 0,1,...,h(s) に対して i ⊕ s = i+s

がなりたつための必要十分条件は

s=u × 2^v かつ h(s) = ⌊

⌋ < 2^v

となるu ∈ Z_{≥ 0}が存在することであり，それは条件( 105)が正しいための必要十分条件である．したがって定理 3.1よりこの系の証明を終える.

[1]: S. Nakamura and R. Miyadera, Impartial Chocolate Bar Games, Integers Volume 15, 2015.
[2]: A.C.Robin, A poisoned chocolate problem, Problem corner, The Mathematical Gazette Vol. 73, No. 466 (Dec., 1989), pp. 341-343. An Answer for the above problem is in Vol. 74, No. 468, June 1990, pp. 171-173.
[3]: D.Zeilberger, Three-Rowed CHOMP, Adv. Applied Math Vol. 26 (2001), pp. 168-179.
[4]: M. H. Albert, R. J. Nowakowski and D. Wolfe, Lessons In Play, A K Peters, p-139.
[5]: A.N.Siegel, Combinatorial Game Theory (Graduate Studies in Mathematics), American Mathematical Society (2013).

HOME