3.1 A Sufficient Condition for a Chocolate Bar $CB(f,y,z)$ to have the Grundy Number $G(\{ y,z\} )=y \oplus z$

In this subsection we study a sufficient condition for a chocolate bar $CB(f,y,z)$ to have a Grundy number $G(\{ y,z\} ) = y \oplus z$.

In our proofs, it will be useful to have the disjunctive sum of a chocolate bar $CB(f,y,z)$ to the right of the bitter square and a single strip of chocolate bar to the left, as in Figures 3.1, 3.2, 3.3, 3.4, 3.5 and 3.6. We will denote such a position by $\{ x,y,z\} $, where $x$ is the length of the single strip of chocolate bar and $y,z$ are coordinates of $CB(f,y,z)$. Figures 3.4, 3.5 and 3.6 give some examples of the coordinate system. For the disjunctive sum of the chocolate bar game with $CB(f,y,z)$ to the right of the bitter square and a single strip of chocolate bar to the left, we will show that the $\mathcal{P}$-positions are when $x\oplus y\oplus z=0$, so that the Grundy number of the chocolate bar $CB(f,y,z)$ is $x$ $ =y\oplus z$.

Example 3.1.    Examples of coordinates of chocolate bar games.

 

fig3.1

Figure 3.1.

{4,7,12}

fig3.2

Figure 3.2.

{3,5,10}

 

fig3.3

Figure 3.3.

{0,4,6}

 

 

fig3.4

Figure 3.4.

$\{ 3,4,9\} $

 

fig3.5

 

Figure 3.5.

$\{ 4,3,13\} $

fig3.6

Figure 3.6.

$\{ 2,3,13\} $

$move_ h (\{ x, y, z\} )$ is the set that contains all the positions that can be reached from the position $\{ x, y, z\} $ in one step (directly).

Definition 3.1.   For $x,y,z \in Z_{\ge 0}$, we define
$move_ h(\{ x,y,z\} )=\{ \{ u,y,z \} :u<x \} \cup \{ \{ x,v,z \} :v<y \} \cup \{ \{ x,\min (y, h(w) ),w \} :w<z \} $, where $u,v,w \in Z_{\ge 0}$.

The following condition $(a)$ in Definition 3.2 is a sufficient condition for a chocolate bar $CB(f,y,z)$ to have a Grundy number $G(\{ y,z\} ) = y \oplus z$.

Definition 3.2.  Let $h$ be a function of $Z_{\geq 0}$ into $Z_{\geq 0}$ that satisfies the conditions of Definition 2.1. and the following condition $(a)$.
$(a)$ Suppose that

  \begin{equation} \label{aaconditionforh} \lfloor \frac{z}{2^ i}\rfloor = \lfloor \frac{z^{\prime }}{2^ i}\rfloor \end{equation}   (3.1)

for some $z,z^{\prime } \in Z_{\geq 0}$ and some natural number $i$. Then we have

  \begin{equation} \label{aaconditionforh2} \lfloor \frac{h(z)}{2^{i-1}}\rfloor = \lfloor \frac{h(z^{\prime })}{2^{i-1}}\rfloor . \end{equation}   (3.2)

Remark 3.1. The condition $(a)$ of Definition 3.2 is equivalent to the following condition $(b)$.
$(b)$ Suppose that $z_ k,y_ k \in \{ 0,1\} $ for $k = 0,1,...,n$ and

  \begin{equation} \label{conditionforh} h(\sum \limits _{k = 0}^ n {{z_ k}} {2^ k})=\sum \limits _{k = 0}^ n {{y_ k}} {2^ k}.\nonumber \end{equation}    

Let $i$ be a natural number. Then for any $z_ k^{\prime } \in \{ 0,1\} $ for $k=0,...,i-1$ there exist $y_ k^{\prime } \in \{ 0,1\} $ for $k=0,...,i-2$ such that

  \begin{equation} \label{conditionforh2} h(\sum \limits _{k = i}^ n {{z_ k}} {2^ k} + \sum \limits _{k = 0}^{i-1} {{z_ k^{\prime }}} {2^ k}) = \sum \limits _{k = i-1}^ n {{y_ k}} {2^ k} + \sum \limits _{k = 0}^{i-2} {{y_ k^{\prime }}} {2^ k}.\nonumber \end{equation}    

The condition $(a)$ of Definition 3.2 is very abstract, so we present some examples of functions that satisfy condition $(a)$ of Definition 3.2 in Lemma 3.1 and Lemma3.2.

Lemma 3.1.    Let $h(z)=\lfloor \frac{z}{2k}\rfloor $ for some natural number $k$. Then $h(z)$ satisfies the condition of Definition 3.2. We prove the contraposition of the condition of Definition 3.2. We suppose that Equation (3.2) is false. Then there exist $u \in Z_{\geq 0}$ and a natural number $i$ such that

  \begin{equation} \label{falseofformer} \lfloor \frac{\lfloor \frac{z}{2k} \rfloor }{2^{i-1}}\rfloor = u < u+1 \leq \lfloor \frac{\lfloor \frac{z^{\prime }}{2k} \rfloor }{2^{i-1}}\rfloor . \end{equation}   (3.3)

We prove that Equation (3.1) is false. From the inequality in (3.3), we have

  \begin{equation} \lfloor \frac{z}{2k} \rfloor \leq u2^{i-1}+2^{i-1}-1 < (u+1)2^{i-1} \leq \lfloor \frac{z^{\prime }}{2k} \rfloor ,\nonumber \end{equation}    

and hence

  \begin{equation} \label{multplefy2k} z \leq 2k(u2^{i-1}+2^{i-1}-1)+2k-1 < 2k(u+1)2^{i-1} \leq z^{\prime }. \end{equation}   (3.4)

From the inequality in (3.4), we have

  \begin{equation} \frac{z}{2^ i} \leq k(u+1)-\frac{1}{2^ i} < k(u+1) \leq \frac{z^{\prime }}{2^ i}.\nonumber \end{equation}    

Therefore we have

  \begin{equation} \lfloor \frac{z}{2^ i} \rfloor < k(u+1) \leq \lfloor \frac{z^{\prime }}{2^ i} \rfloor .\nonumber \end{equation}    

This shows that Equation (3.1) is false. Therefore, we have completed the proof of this lemma.

Lemma 3.2.    Let $h(0) = h(1)=0$ and $h(z)=2^{\lfloor log_2z\rfloor -1}$ for $z \in Z_{\geq 0}$ such that $z \geq 2$. Then $h(z)$ satisfies the condition of Definition 3.2. We prove the contraposition of the condition of Definition 3.2. Suppose that Equation (3.2) is false. Then for a natural number $i$

  \begin{equation} \label{falseofflog1} \lfloor \frac{2^{\lfloor log_2z\rfloor -1}}{2^{i-1}}\rfloor < \lfloor \frac{2^{\lfloor log_2z^{\prime }\rfloor -1}}{2^{i-1}}\rfloor . \end{equation}   (3.5)

We prove that Equation (3.1) is false. Let $z = 2^{n+m}$ and $z^{\prime }=2^{n^{\prime }+m^{\prime }}$ such that $n, n^{\prime } \in Z_{\geq 0}$ and $0 \leq m,m^{\prime } < 1$. Then by the inequality in (3.5), we have

  \begin{equation} \label{falseofflog2} \lfloor 2^{n-i} \rfloor < \lfloor 2^{n^{\prime }-i} \rfloor . \end{equation}   (3.6)

By the inequality in (3.6), we have

 
$\displaystyle n^{\prime } - i \geq 0\label{agrulog1} $
(3.7)
  $\displaystyle \text {and } \nonumber $    
  $\displaystyle n+1 \leq n^{\prime }.\label{agrulog2} $ (3.8)

By the inequalities in (3,7) and (3.8), we have

  \begin{equation} \lfloor \frac{z}{2^ i} \rfloor = \lfloor 2^{n+m-i} \rfloor < 2^{n^{\prime }-i} \leq \lfloor 2^{n^{\prime }+m^{\prime }-i} \rfloor = \lfloor \frac{z^{\prime }}{2^ i} \rfloor .\nonumber \end{equation}    

This shows that Equation (3.1) is false. Therefore we have completed the proof.

In the remainder of this subsection we assume that $h$ is the function that satisfies the condition $(a)$ in Definition 3.2. Our aim is to show that the disjunctive sum of the chocolate bar game with $CB(f,y,z)$ to the right of the bitter square and a single strip of chocolate bar to the left have $\mathcal{P}$-positions when $x\oplus y\oplus z=0$, so that the Grundy number of the chocolate bar $CB(f,y,z)$ is $x$ $ =y\oplus z$.

We need Lemma3.6and Lemma3.7  for this aim. Lemma 3.6 implies that from a position $\{ x,y,z\} $ of the disjunctive sum such that $x \oplus y \oplus z \neq 0$ you always have a option that leads to a position for which the nim-sum of the coordinates is $0$. Lemma 3.7 implies that from a position $\{ x,y,z\} $ of the disjunctive sum such that $x \oplus y \oplus z = 0$ any option leads to a position for which the nim-sum of the coordinates is not $0$.
To prove Lemma 3.6 and Lemma 3.7 we need some properties of the function $h$ that satisfies the condition $(a)$ in Definition 3.2. These properties are proved in Lemma 3.3, Lemma 3.4 and Lemma 3.5.

Lemma 3.3. Suppose that

  \begin{equation} \label{eqlemmaforh1} h(\sum \limits _{k = 0}^ n {{z_ k}} {2^ k}) \geq \sum \limits _{k = 0}^ n {{y_ k}} {2^ k}. \end{equation}   (3.9)

Then, for any natural number $i$,

  \begin{equation} \label{eqlemmaforh2} h(\sum \limits _{k = i}^ n {{z_ k}} {2^ k}) \geq \sum \limits _{k = i-1}^ n {{y_ k}} {2^ k}.\nonumber \end{equation}    

Proof. Let $h(\sum \limits _{k = 0}^ n {{z_ k}} {2^ k}) = \sum \limits _{k = 0}^ n {{u_ k}} {2^ k}$ for $u_ k \in \{ 0,1\} $. Then, by the inequality in (3.9),

 

 

  \begin{equation} \label{eqqq1} \sum \limits _{k = 0}^ n {{u_ k}} {2^ k} \geq \sum \limits _{k = 0}^ n {{y_ k}} {2^ k}, \nonumber \end{equation}    

and hence

  \begin{equation} \label{eqqq2} \sum \limits _{k = i-1}^ n {{u_ k}} {2^ k} \geq \sum \limits _{k = i-1}^ n {{y_ k}} {2^ k}. \end{equation}   (3.10)

Let $z_ k^{\prime } = 0$ for $k = 0,1,2,...,i-1$. By the inequality in (3.10), Definition 3.2 and Remark 3.1, there exist $y_ k^{\prime }$ for $k=0,...,i-2$ such that

  \begin{equation} \label{eqlemmaforh3} h(\sum \limits _{k = i}^ n {{z_ k}} {2^ k}) = h(\sum \limits _{k = i}^ n {{z_ k}} {2^ k} + \sum \limits _{k = 0}^{i-1} {{z_ k^{\prime }}} {2^ k}) = \sum \limits _{k = i-1}^ n {{u_ k}} {2^ k} + \sum \limits _{k = 0}^{i-2} {{y_ k^{\prime }}} {2^ k} \geq \sum \limits _{k = i-1}^ n {{u_ k}} {2^ k} \geq \sum \limits _{k = i-1}^ n {{y_ k}} {2^ k}.\nonumber \end{equation}    

Lemma 3.4.

$(i)$ Suppose that for some natural number $i$

  \begin{equation} \label{eqlemmaforh21} h(\sum \limits _{k = i}^ n {{p_ k}} {2^ k}) < \sum \limits _{k = i-1}^ n {{q_ k}} {2^ k}. \end{equation}   (3.11)

Then

  \begin{equation} \label{eqlemmaforh22} h(\sum \limits _{k = 0}^ n {{p_ k}} {2^ k}) < \sum \limits _{k = i-1}^ n {{q_ k}} {2^ k}.\nonumber \end{equation}    

$(ii)$ Suppose that

  \begin{equation} \label{eqlemmaforh21b} h(\sum \limits _{k = 0}^ n {{p_ k}} {2^ k}) \geq \sum \limits _{k = i-1}^ n {{q_ k}} {2^ k}.\nonumber \end{equation}    

Then

  \begin{equation} \label{eqlemmaforh22b} h(\sum \limits _{k = i}^ n {{p_ k}} {2^ k}) \geq \sum \limits _{k = i-1}^ n {{q_ k}} {2^ k}. \nonumber \end{equation}    

We prove $(i)$. Let $h(\sum \limits _{k = 0}^ n {{p_ k}} {2^ k})= \sum \limits _{k = 0}^ n {{r_ k}} {2^ k}$ for $r_ k \in \{ 0,1\} $. Then, by Remark 3.1, there exist $r_ k^{\prime }$ for $k=0,1,2,...,i-2$ such that $h(\sum \limits _{k = i}^ n {{p_ k}} {2^ k}) $ $= \sum \limits _{k = i-1}^ n {{r_ k}} {2^ k}+\sum \limits _{k = 0}^{i-2} {{r_ k^{\prime }}} {2^ k}$. Then, by the inequality in (3.11), we have

  \begin{equation} \label{eqlemmaforh23} \sum \limits _{k = i-1}^{n} {{q_ k}} {2^ k} > \sum \limits _{k = i-1}^ n {{r_ k}} {2^ k}+\sum \limits _{k = 0}^{i-2} {{r_ k^{\prime }}} {2^ k},\nonumber \end{equation}    

and hence we have the inequality in (3.12) or Relation (3.13).

  \begin{equation} \label{firstcasefor} q_ n > r_ n. \end{equation}   (3.12)

There exists $j \in Z_{\geq 0}$ such that

  \begin{equation} \label{secondcasefor} i-1 \leq j \leq n, q_ k = r_ k \text { for } k = j+1,j+2,...,n \text { and } q_ j > r_ j. \end{equation}   (3.13)

Then, by the inequality in (3.12) or Relation (3.13),

  \begin{equation} \label{eqlemmaforh24} \sum \limits _{k = i-1}^{n} {{q_ k}} {2^ k} > \sum \limits _{k = i-1}^ n {{r_ k}} {2^ k}+\sum \limits _{k = 0}^{i-2} {{r_ k}} {2^ k} = \sum \limits _{k = 0}^ n {{r_ k}} {2^ k}=h(\sum \limits _{k = 0}^ n {{p_ k}} {2^ k}).\nonumber \end{equation}    

We prove $(ii)$. This is the contraposition of the proposition in $(i)$ of this lemma.

Lemma 3.5. Suppose that

  \begin{equation} \label{eqlemmaforh212} h(\sum \limits _{k = i}^ n {{p_ k}} {2^ k}) < \sum \limits _{k = i-1}^ n {{q_ k}} {2^ k}+2^{i-1}. \end{equation}   (3.14)

Then

  \begin{equation} \label{eqlemmaforh222} h(\sum \limits _{k = i-1}^ n {{p_ k}} {2^ k}) < \sum \limits _{k = i-1}^ n {{q_ k}} {2^ k}+2^{i-1}.\nonumber \end{equation}    

Proof. Let $\sum \limits _{k = i-1}^{n+1} {{q^{\prime }_ k}} {2^ k} = \sum \limits _{k = i-1}^ n {{q_ k}} {2^ k}+2^{i-1}$ and $p_{n+1}=0$. Then, by the inequality in (3.14), we have $h(\sum \limits _{k = i}^{n+1} {{p_ k}} {2^ k}) < \sum \limits _{k = i-1}^{n+1} {{q^{\prime }_ k}} {2^ k}$, and statement $(i)$ of Lemma 3,4 implies $ h(\sum \limits _{k = i-1}^ n {{p_ k}} {2^ k}) \leq h(\sum \limits _{k = 0}^{n+1} {{p_ k}} {2^ k}) < \sum \limits _{k = i-1}^{n+1} {{q^{\prime }_ k}} {2^ k}$ $=\sum \limits _{k = i-1}^ n {{q_ k}} {2^ k}+2^{i-1}$. Therefore we have completed the proof of this lemma.

If the nim-sum of the cooridinates of a position is not 0, then by Definition 3.1and the following Lemma 3.6, there is always an option that leads to a position whose nim-sum is 0.

Lemma 3.6. Suppose that $x \oplus y \oplus z \neq 0$ and

  \begin{equation} \label{inequalityyz} y \leq h(z). \end{equation}   (3.15)

Then at least one of the following statements is true.
$(1)$ $u\oplus y\oplus z= 0$ for some $u\in Z_{\geq 0}$ such that $u<x$.
$(2)$ $x\oplus v\oplus z= 0$ for some $v\in Z_{\geq 0}$ such that $v<y$.
$(3)$ $x\oplus y\oplus w= 0$ for some $w\in Z_{\geq 0}$ such that $w<z$ and $y \leq h(w)$.
$(4)$ $x\oplus v\oplus w^{\prime }= 0$ for some $v,w^{\prime } \in Z_{\geq 0}$ such that $v<y,w^{\prime } <z$ and $v=h(w^{\prime })$.
Proof. Let $x= \sum \limits _{k = 0}^ n {{x_ k}} {2^ k}$, $y= \sum \limits _{k = 0}^ n {{y_ k}} {2^ k}$ and $z= \sum \limits _{k = 0}^ n {{z_ k}} {2^ k}$. If $n=0$, then this lemma is obvious. We assume that $n \geq 1$. Suppose that there exists a non-negative integer $s$ such that $x_ i + y_ i + z_ i = 0 \ (mod \ 2)$ for $i = n,n-1,...,n-s$ and

  \begin{equation} \label{xyznminush} x_{n-s-1} + y_{n-s-1} + z_{n-s-1} \neq 0 \ (mod \ 2). \end{equation}   (3.16)

Case $(i)$ Suppose that $x_{n-s-1}=1$. Then, we define $u = \sum ^{n}_{i=1}u_ i2^ i$ by $u_ i=x_ i$ for $i=n,n-1,..., n-s $, $u_{n-s-1}=0<x_{n-s-1}$ and $u_ i=y_ i+z_ i$ $( mod \ 2 )$ for $i=n-s-2,n-s-3,...,0$. Then we have $u \oplus y \oplus z = 0$ and $u<x$. Therefore, we have statement $(1)$ of this lemma.
Case $(ii)$ Suppose that $y_{n-s-1}=1$. Then, by the method that is similar to the one used in $(i)$, we prove that $x \oplus v \oplus z = 0$ for some $v \in Z_{\geq 0}$ such that $v<y$. Therefore we have statement $(2)$ of this lemma.
Case $(iii)$ We suppose that

  \begin{equation} \label{xyztonmink} z_{n-s-1} =1. \end{equation}   (3.17)

For $i = n,n-1,...,n-s$, let

  \begin{equation} \label{fromntonminask} w_ i = z_ i. \end{equation}   (3.18)

Let $w_ i = x_ i + y_ i \ (mod \ 2)$ for $i=n-s-1,...,0$. By the inequality in (3.16) and Equation (3.17), we have $w_{n-s-1}$ $=x_{n-s-1}+y_{n-s-1} = 0$ $(mod \ 2)$, and hence

  \begin{equation} \label{newinnauai1} w_{n-s-1}=0 < 1 = z_{n-s-1}. \end{equation}   (3.19)

Subcase $(iii.1)$ If $y \leq h(w)$, then we have statement $(3)$ of this lemma.
Subcase $(iii.2)$ Next we suppose that

  \begin{equation} \label{ybiggernthanhw} y > h(w). \end{equation}   (3.20)

By the inequality in (3.15), we have $\sum \limits _{k = 0}^ n {{y_ k}} {2^ k} \leq h(\sum \limits _{k = 0}^ n {{z_ k}} {2^ k})$, and hence by Lemma 3.3 and (3.18)

  \begin{equation} \label{untilies1} \sum \limits _{k = n-s-1}^ n {{y_ k}} {2^ k} \leq h(\sum \limits _{k = n-s}^ n {{z_ k}} {2^ k})=h(\sum \limits _{k = n-s}^ n {{w_ k}} {2^ k}) \leq h(w). \end{equation}   (3.21)

By the inequalities in (3.21) and (3.20), there exists a natural number $j$ such that

  $\displaystyle \sum \limits _{k = n-j}^ n {{y_ k}} {2^ k} \leq h(\sum \limits _{k = 0}^ n {{w_ k}} {2^ k}) =h(w)\label{e1quationse31} $   (3.22)
  $\displaystyle \text {and} \sum \limits _{k = n-j-1}^ n {{y_ k}} {2^ k} > h(\sum \limits _{k = 0}^ n {{w_ k}} {2^ k})=h(w) .\label{e1quationse32} $   (3.23)

By the inequalities in (3.21) and (3.23),

  \begin{equation} \label{star1ineq} n-j-1 < n-s-1. \end{equation}   (3.24)

By the inequality in (3.22) and $(ii)$ of Lemma 3.4,

  \begin{equation} \label{e1quationse31b} \sum \limits _{k = n-j}^ n {{y_ k}} {2^ k} \leq h(\sum \limits _{k = n-j+1}^ n {{w_ k}} {2^ k})\leq h(\sum \limits _{k = n-j}^ n {{w_ k}} {2^ k}). \end{equation}   (3.25)

By the inequality in (3.23),

  \begin{equation} \label{e1quationse32b} \sum \limits _{k = n-j-1}^ n {{y_ k}} {2^ k} > h(\sum \limits _{k = n-j}^ n {{w_ k}} {2^ k}). \end{equation}   (3.26)

By the inequalities in (3.25) and (3.26), we have

  \begin{equation} \label{e1quationse31and31b} \sum \limits _{k = n-j}^ n {{y_ k}} {2^ k} \leq h(\sum \limits _{k = n-j}^ n {{w_ k}} {2^ k}) < \sum \limits _{k = n-j-1}^ n {{y_ k}} {2^ k}. \end{equation}   (3.27)

We construct $v$ and $w^{\prime }$ by assigning values to $v_ i$ and $w_ i^{\prime }$ for $i = n,n-1,n-2,...,0$. First, for $i = n,n-1,...,n-j$, let

  \begin{equation} \label{constructvandwprime} w_ i^{\prime } = w_ i \text { \ and } v_ i = y_ i, \end{equation}   (3.28)

and let

  \begin{equation} \label{star2ineq} v_{n-j-1} = 0 < 1 = y_{n-j-1} \end{equation}   (3.29)

and

  \begin{equation} w_{n-j-1}^{\prime }=x_{n-j-1} + v_{n-j-1}. \nonumber \end{equation}    

Since $v_{n-j-1} = 0$ and $y_{n-j-1}=1$, by the inequality in (3.27)

  \begin{equation} \label{constru1} \sum \limits _{k = n-j-1}^ n {{v_ k}} {2^ k} \leq h(\sum \limits _{k = n-j}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = n-j-1}^ n {{v_ k}} {2^ k} + 2^{n-j-1}. \end{equation}   (3.30)

By the inequality in (3.30) and Lemma 3.5, we have

  \begin{equation} \label{constru1b} \sum \limits _{k = n-j-1}^ n {{v_ k}} {2^ k} \leq h(\sum \limits _{k = n-j-1}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = n-j-1}^ n {{v_ k}} {2^ k} + 2^{n-j-1}. \end{equation}   (3.31)

Next we prove the inequality in (3.32) for any $t=n-j-1, n-j-2,...,2,1,0$ recursively.

  \begin{equation} \label{construct1} \sum \limits _{k = t}^ n {{v_ k}} {2^ k} \leq h(\sum \limits _{k = t}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = t}^ n {{v_ k}} {2^ k} + 2^ t. \end{equation}   (3.32)

By the inequality in (3.31), we have the inequality in (3.32) for $t = n-j-1$. We suppose the inequality in (3.32) for some natural number $t$ such that $t \leq n-j-1$. Then we have the inequality in (3.33) or the inequality in (3.36). Our aim is to prove (3.35) and (3.38) by using these inequalities.

If

  \begin{equation} \label{construct2} \sum \limits _{k = t}^ n {{v_ k}} {2^ k}+2^{t-1} \leq h(\sum \limits _{k = t}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = t}^ n {{v_ k}} {2^ k}+2^{t}, \end{equation}   (3.33)

then let $v_{t-1}=1$ and $w_{t-1}^{\prime }=x_{t-1}+ v_{t-1}$ $(mod \ 2)$. Since $v_{t-1}=1$, by the inequality in (3.33) we have

  \begin{equation} \label{construct3} \sum \limits _{k = t-1}^ n {{v_ k}} {2^ k} \leq h(\sum \limits _{k = t}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = t-1}^ n {{v_ k}} {2^ k}+2^{t-1}. \end{equation}   (3.34)

Note that $v_{t-1}2^{t-1} + 2^{t-1} = 2^ t$. By Lemma 3.5 and the inequality in (3.34),

  \begin{equation} \label{construct3b} \sum \limits _{k = t-1}^ n {{v_ k}} {2^ k} \leq h(\sum \limits _{k = t-1}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = t-1}^ n {{v_ k}} {2^ k}+2^{t-1}. \end{equation}   (3.35)

If

  \begin{equation} \label{construct4} \sum \limits _{k = t}^ n {{v_ k}} {2^ k}+2^{t-1} > h(\sum \limits _{k = t}^ n {{w_ k^{\prime }}} {2^ k}), \end{equation}   (3.36)

then let $v_{t-1}=0$ and $w_{t-1}^{\prime }=x_{t-1}+ v_{t-1}$ $(mod \ 2)$.
Since $v_{t-1}=0$, the inequalities in (3.36) and (3.32) give

  \begin{equation} \label{construct5} \sum \limits _{k = t-1}^ n {{v_ k}} {2^ k} \leq h(\sum \limits _{k = t}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = t-1}^ n {{v_ k}} {2^ k}+2^{t-1}. \end{equation}   (3.37)

Then, by the inequality in (3.37) and Lemma 3.5, we have

  \begin{equation} \label{construct5b} \sum \limits _{k = t-1}^ n {{v_ k}} {2^ k} \leq h(\sum \limits _{k = t-1}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = t-1}^ n {{v_ k}} {2^ k}+2^{t-1}. \end{equation}   (3.38)

In this way we get the inequality in (3.35) or the inequality in (3.38) by the inequality in (3.32). Note that the inequality in (3.35) and the inequality in (3.38) are the same inequality. By continuing this process we have

  \begin{equation} \sum \limits _{k = 0}^ n {{v_ k}} {2^ k} \leq h(\sum \limits _{k = 0}^ n {{w_ k^{\prime }}} {2^ k}) < \sum \limits _{k = 0}^ n {{v_ k}} {2^ k}+2^{0}.\nonumber \end{equation}    

Therefore, we have $\sum \limits _{k = 0}^ n {{v_ k}} {2^ k} = h(\sum \limits _{k = 0}^ n {{w_ k^{\prime }}} {2^ k}).$ By iequalities (3.19), (3.24), (3.29) and Equation (3.28), we have $v < y$ and $w^{\prime } < z$. Therefore, we have statement $(4)$ of this lemma. If the nim-sum of the cooridinates of a position is 0, then by Definition 3.1 and the following Lemma 3.7, any option from this position leads to a position whose nim-sum is not 0.

Lemma 3.7.   If $x \oplus y \oplus z = 0$ and $y \le h(z)$ , then the following hold:
$(i)$ $u \oplus y \oplus z \ne 0$ for any $u \in {Z_{ \ge 0}}$ such that $u<x$.
$(ii)$ $x \oplus v \oplus z \ne 0$ for any $v \in {Z_{ \ge 0}}$ such that $v<y$.
$(iii)$ $x \oplus y \oplus w \ne 0$ for any $w \in {Z_{ \ge 0}}$ such that $w<z$.
$(iv)$ $x \oplus v \oplus w \ne 0$ for any $v,w \in {Z_{ \ge 0}}$ such that $v<y,w<z$ and $v= h(w)$. Statements $(i)$,$(ii)$ and $(iii)$ of this lemma follow directly from Definition 1 (the definition of nim-sum).
We now prove statement $(iv)$. We suppose that $v= h(w)$ for some $w\in Z_{\geq 0}$ such that $v<y,w<z$. We also suppose that

  \begin{equation} \label{construct6a} w_ i=z_ i \text { for } i = n,n-1,n-2,...,j \text { and } w_{j-1}<z_{j-1}. \end{equation}   (3.39)

By $y \le h(z)$, we have $h(\sum \limits _{k = 0}^ n {{z_ k}} {2^ k}) \geq \sum \limits _{k = 0}^ n {{y_ k}} {2^ k}$. Hence, by Lemma 3.3, we have

  \begin{equation} \label{construct6} h(\sum \limits _{k = j}^ n {{z_ k}} {2^ k}) \geq \sum \limits _{k = j-1}^ n {{y_ k}} {2^ k}. \end{equation}   (3.40)

Since $v= h(w)$ and $v < y$, Relation (3.39) gives

  \begin{equation} \label{construct7} h(\sum \limits _{k = j}^ n {{z_ k}} {2^ k}) = h(\sum \limits _{k = j}^ n {{w_ k}} {2^ k}) \leq h(w) = v = \sum \limits _{k = 0}^ n {{v_ k}} {2^ k} < \sum \limits _{k = 0}^ n {{y_ k}} {2^ k}. \end{equation}   (3.41)

By the inequalities in (3.40) and (3.41), we have

  \begin{equation} \sum \limits _{k = j-1}^ n {{y_ k}} {2^ k} \leq \sum \limits _{k = 0}^ n {{v_ k}} {2^ k} < \sum \limits _{k = 0}^ n {{y_ k}} {2^ k}. \nonumber \end{equation}    

Hence, for $k = n,n-1,n-2,...,j-1$,

  \begin{equation} \label{conditionyv1} v_{k}=y_{k}. \end{equation}   (3.42)

Since $x \oplus y \oplus z = 0$, we have

  \begin{equation} \label{conditionyv2} x_{j-1}+y_{j-1}+z_{j-1} = 0 \ (mod \ 2). \end{equation}   (3.43)

By Relation (3.39), Equation (3.42) and Equation (3.43), we have $x_{j-1}+v_{j-1}+w_{j-1} \neq 0 \ (mod \ 2)$, and hence $x \oplus v \oplus w \neq 0$.

Let $A_{h}=\{ \{ x,y,z\} :x,y,z\in Z_{\geq 0},y \leq h(z) $ and $x\oplus y \oplus z=0\} $ and $B_{h}=\{ \{ x,y,z\} :x,y,z\in Z_{\geq 0},y \leq h(z)$ and $x\oplus y \oplus z\neq 0\} $.

Let $A_ h$ and $B_ h$ be the sets defined in Definition 3.3. Then the following hold:
$(i)$ If we start with a position in $A_ h$, then any option (move) leads to a position in $B_ h$.
$(ii)$ If we start with a position in $B_ h$, then there is at least one option (move) that leads to a position in $A_ h$.
Since $move_ h (\{ x, y, z\} )$ that is defined in Definition 3.1 contains all the positions that can be reached from the position $\{ x, y, z\} $ in one step, we have statements $(i)$ and $(ii)$ by Lemma 3.7 and Lemma 3.6 respectively.

Theorem 3.1. Let $A_ h$ and $B_ h$ be the sets defined in Definition 3.3. $A_ h$ is the set of $\mathcal{P}$-positions and $B_ h$ is the set of $\mathcal{N}$-positions of the disjunctive sum of the chocolate bar game with $CB(h,y,z)$ to the right of the bitter square and a single strip of chocolate bar to the left. If we start the game from a position $\{ x,y,z\} \in A_{h}$, then Lemma 3.8 indicates that any option we take leads to a position $\{ p,q,r\} $ in $B_ h$. From this position $\{ p,q,r\} $, Lemma 3.8 implies that our opponent can choose a proper option that leads to a position in $A_ h$. Note that any option reduces some of the numbers in the coordinates. In this way, our opponent can always reach a position in $A_ h$, and will finally win by reaching $\{ 0,0,0\} \in A_{h}$. Note that position $\{ 0,0,0\} $ represent the bitter square itself, and we cannot eat this part. Therefore $A_ h$ is the set of $\mathcal{P}$-positions.
If we start the game from a position $\{ x,y,z\} \in B_{h}$, then Lemma 3.8 means that we can choose a proper option that leads to a position $\{ p,q,r\} $ in $A_ h$. From $\{ p,q,r\} $, Lemma 3.8 implies that any option taken by our opponent leads to a position in $B_ h$. In this way we win the game by reaching $\{ 0, 0, 0\} $. Note that our opponent cannot eat the bitter part. Therefore $B_ h$ is the set of $\mathcal{N}$-position

Theorem 3.2 Let $h$ be the function that satisfies the condition $(a)$ in Definition 3.2. Then the Grundy number of $CB(h,y,z)$ is $ y \oplus z$.

Proof. By Theorem 3.1, a position $\{ x,y,z\} $ of the sum of the chocolate bars is a $\mathcal{P}$-position when $x\oplus y\oplus z=0$. Therefore, Theorem 1.1 implies that the Grundy number of the chocolate bar to the right is $x$ $ = y\oplus z$.

 

By Theorem 3,2, the condition of Definition 3.2 is a sufficient condition for the chocolate bar $CB(h,y,z)$ to have the Grundy number $G(\{ y,z\} ) = y \oplus z$. Lemma 3.1, Lemma 3.2 and Theorem 3.2 imply that chocolate bar games in Figure 2.1, Figure 2.2, Figure 2.3 and Figure 2.4 have the Grundy number $G(\{ y,z\} ) = y \oplus z$.

In the next subsection we prove that the condition of Definition 3.2 is a necessary condition for the chocolate bar $CB(h,y,z)$ to have the Grundy number $G(\{ y,z\} ) = y \oplus z$.

A Necessary Condition for a Chocolate Bar to have the Grundy Number y⊕Z