4.1 A Sufficient Condition for a Chocolate Bar to have the Grundy Number $(y \oplus (z+s))-s$

Let $h$ be the function that satisfies the condition $(a)$ in Definition 3.2 and let $G_ h(\{ y,z\} )$ be the Grundy number of $CB(h,y,z)$. The condition $(a)$ in Definition 3.2 is a necessary and sufficient condition for $CB(h,y,z)$ to have the Grundy number $G_ h(\{ y,z\} )=y \oplus z$, and we can use all the lemmas and theorems in previous sections for the function $h$ and $CB(h,y,z)$.

Definition 4.1. We define the function $h_ s$ as the followings.
Let $s$ be a natural number such that

  \begin{equation} \nonumber i \oplus s = i + s \text { for } i = 0,1,2,...,h(s). \end{equation}    

Let $h_ s(z) = h(z+s)$ for any $z \in Z_{\geq 0}$.

We are going to show that the condition in Definition 4.1 is a necessary and sufficient condition for the chocolate bar $CB(h_ s,y,z)$ to have the Grundy number $G_{h_ s}(\{ y,z\} )= (y \oplus (z+s))-s$.

Lemma 4.1. Let $p \in Z_{\geq 0}$ and $s$ be a natural number. Then

  \begin{equation} \label{conditionfoforp} i \oplus s = i+s \text { for } i = 0,1,...,p \end{equation}   (4.5)

if and only if there exist a natural number $u$ and a non-negative integer $v$ such that

  \begin{equation} \label{conditionfoforp2} s = u \times 2^{v} \text { and } 2^{v} > p. \end{equation}   (4.6)

Proof. We suppose Relation (4.5). When $p > 0$, let $p=\sum \limits _{k = 0}^{t} {{p_ k}} {2^ k}$ with $p_ t=1$ and $p_ k \in \{ 0,1\} $. Let $s = \sum \limits _{k = 0}^{n} {{s_ k}} {2^ k}$ with $s_ n=1$ and $s_ k \in \{ 0,1\} $. Since $p \oplus s = p+s$ and $p_ t=1$, $s_ t=0$. Since $0 \leq \sum \limits _{k = 0}^{t-1} {} {2^ k} < p$, $\sum \limits _{k = 0}^{t-1} {} {2^ k} \oplus s = \sum \limits _{k = 0}^{t-1} {} {2^ k} + s$. Therefore, $s_ i = 0$ for $i = 0,1,...,t-1$. Let $u = \sum \limits _{k = t+1}^{n} {s_ k} {2^{k-t-1}} $ and $v=t+1$, then we have Relation (4.6). When $p=0$, we let $v=0$ and $u=s$. Then we have Relation (4.6).

Next we suppose that there exist a natural number $u$ and a non-negative integer $v$ that satisfy Relation (4.6). Then it is clear that we have Relation (4.5).

Lemma 4.2. Let $p \in Z_{\geq 0}$ and $s$ be a natural number such that $i \oplus s = i+s$ for $i = 0,1,...,p$. Let $j \in Z_{\geq 0}$ such that $0 \leq j \leq p$. Then

  \begin{equation} \label{thissetequalthatset} \text {the set } \{ j \oplus i:i=0,1,2,...,s-1 \} \text { is the same as the set } \{ 0,1,2,...,s-1\} . \end{equation}   (4.7)

Proof. By Lemma 4.1, there exist a natural number $u$ and a non-negative integer $v$ such that $s = u \times 2^{v}$ and $2^{v} > p$.

Let $j \in Z_{\geq 0 } $ such that $0 \leq j \leq p$. Then we write $j$ in base 2, and we have $j = \sum \limits _{k = 0}^{v-1} {{j_ k}} {2^ k}$. We prove that $0 \leq j \oplus i \leq s-1$ for $0 \leq i \leq s-1$. Let $i \in Z_{\geq 0 } $ such that

$0 \leq i \leq s-1$. Then there exist $u^{\prime } \in Z_{\geq 0}$ such that $u^{\prime } < u$ and $i = u^{\prime } \times 2^{v} + \sum \limits _{k = 0}^{v-1} {{i_ k}} {2^ k}$ for $i_ k \in \{ 0,1\} $. Therefore,

  \begin{equation} \label{relationji} 0 \leq j \oplus i = u^{\prime } \times 2^{v} + \sum \limits _{k = 0}^{v-1} {{(j_ k \oplus i_ k)}} {2^ k} < u \times 2^{v} = s. \end{equation}   (4.8)

Since $j \oplus i \neq j \oplus i^{\prime }$ for $0 \leq i, i^{\prime } \leq s-1$ such that $i \neq i^{\prime }$, the inequality in (4.8) implies Relation (4.7).

Lemma 4.3. Let $s$ be a natural number, $x \in Z_{\geq 0}$ and $x_ k \in Z_{\geq 0}$ for $k=1,2,...,n$. Suppose that $x,x_ k \geq s$ for $k=1,2,...,n$. Then $\textit{mex}(\{ x_ k:k=1,2,...,n\} \cup \{ 0,1,2,...,s-1\} ) = x$ if and only if $\textit{mex}(\{ x_ k-s:k=1,2,...,n\} ) = x-s$.

Proof. Suppose that $\textit{mex}(\{ x_ k:k=1,2,...,n\} \cup \{ 0,1,2,...,s-1\} ) = x$. By Lemma 1.1, $x \notin \{ x_ k:k=1,2,...,n\} \cup \{ 0,1,2,...,s-1\} $, and hence $x-s \notin \{ x_ k-s:k=1,2,...,n\} $. Let $u \in Z_{\geq 0}$ such that $u<x-s$. Then $u+s<x$, and Lemma 1.1 implies $u+s \in \{ x_ k:k=1,2,...,n\} \cup \{ 0,1,2,...,s-1\} $. Clearly $u+s=x_ k$ for some natural number $k$, and hence $u=x_ k-s$. By Lemma 1.1, we have $\textit{mex}(\{ x_ k-s:k=1,2,...,n\} ) = x-s$.
Conversely we suppose that $\textit{mex}(\{ x_ k-s:k=1,2,...,n\} ) = x-s$. Then, Lemma 1.1 implies $x-s \neq x_ k -s$ for any $k = 0,1,...,n$, and hence $x \neq x_ k$ for any $k = 0,1,...,n$. For any $v \in Z_{\geq 0}$ such that $x > v \geq s$, Lemma 1.1 implies that there exists $u$ such that $v = u +s$ and $x-s > u \geq 0$. By Lemma 1.1, there exists $k$ such that $u = x_ k -s$, and hence we have $v = x_ k$. Therefore Lemma 1.1 implies $\textit{mex}(\{ x_ k:k=1,2,...,n\} \cup \{ 0,1,2,...,s-1\} ) = x$.

Lemma 4.4. Let $s$ be a natural number such that

  \begin{equation} \label{conditionofs1} i \oplus s = i + s \text { for } i = 0,1,2,...,h(s). \end{equation}   (4.9)

Then, for any $y,z \in Z_{\geq 0}$ such that $y \leq h(z+s)$, we have

  $\displaystyle \label{grundyyzpluss} y \oplus (z+s) = G_ h(\{ y,z+s\} ) \hspace{70mm}\nonumber $    
  $\displaystyle = \textit{mex}(\{ v\oplus (z+s):v<y \} \cup \{ 0,1,2,...,s-1\} \cup \{ \min (y,h(w)) \oplus w:s \leq w < z+s\} ). $   (4.10)

In particular $y \oplus (z+s) \geq s$.

Proof. By Theorem 3.2 and the definition of Grundy number,

  $\displaystyle y \oplus (z+s) = G_ h(\{ y,z+s\} ) \hspace{70mm}\nonumber $    
  $\displaystyle =\textit{mex}(\{ G_ h(\{ v,z+s\} ):v<y\} \cup \{ G_ h(\{ \min (y,h(w)),w\} ):w < z+s\} )\nonumber $    
  $\displaystyle =\textit{mex}(\{ G_ h(\{ v,z+s\} ):v<y\} \cup \{ G_ h(\{ \min (y,h(w)),w\} ):w < s\} \nonumber $    
  $\displaystyle \cup \{ G_ h(\{ \min (y,h(w)),w\} ):s \leq w < z+s\} )\label{lastterm1}. $   (4.11)

When $w < s$, we have $h(w) \leq h(s)$, and hence $\min (y,h(w)) = \min ( \min (y,h(s)),h(w))$. Since $\min (y,h(s)) \in Z_{\geq 0}$ and $\min (y,h(s)) \leq h(s)$, Lemma 3.10, Equation (4.9) and Lemma 4.2 imply $\{ 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)) \oplus w:w<s\} $ $=\{ 0,1,2,...,s-1\} $. Hence, by Theorem 3.2,

  $\displaystyle (\ref{lastterm1})=\textit{mex}(\{ v\oplus (z+s):v<y \} \cup \{ 0,1,2,...,s-1\} \cup \{ \min (y,h(w)) \oplus w:s \leq w < z+s \} ).\label{minorchange11} $   (4.12)

Equation (4.11) and Equation (4.12) imply Equation (4.10). Therefore, by Lemma 1, we have $y \oplus (z+s) \geq s$.

Lemma 4.5. Let $s$ be a natural number such that

  \begin{equation} \label{conditionofs2b} i \oplus s = i + s \text { for } i = 0,1,2,...,h(s). \end{equation}   (4.13)

For any $y,z \in Z_{\geq 0}$ such that $y \leq h(z+s)$, we have

  \begin{equation} \label{conditionofstar12} (y \oplus (z+s))-s = \textit{mex}(\{ (v\oplus (z+s))-s:v<y \} \cup \{ ( \min (y,h(w)) \oplus w)-s:s \leq w < z+s \} ). \end{equation}   (4.14)

Proof. By Relation (4.13) and Lemma 4.4, we have $G_ h(\{ y,z+s\} ) $

  \begin{equation} = y \oplus (z+s) = \textit{mex}(\{ v\oplus (z+s):v<y \} \cup \{ 0,1,2,...,s-1\} \cup \{ \min (y,h(w)) \oplus w:s \leq w < z+s \} )\nonumber \end{equation}    
  \begin{equation} = y \oplus (z+s) = \textit{mex}(\{ v\oplus (z+s):v<y \} \cup \{ 0,1,2,...,s-1\} \cup \{ \min (y,h(w^{\prime }+s)) \oplus (w^{\prime }+s):0 \leq w^{\prime } < z \} )\label{grundynimussterm} \end{equation}   (4.15)

for any $y,z \in Z_{\geq 0}$ such that $y \leq h(z+s)$.

Since $v < y \leq h(z+s)$, Lemma 4.4 implies that for $0 \leq v < y$

  \begin{equation} \label{conditionof111} v\oplus (z+s)\geq s. \end{equation}   (4.16)

Since $ \min (y,h(w^{\prime }+s)) \leq h(w^{\prime }+s)$, Lemma 4.4 implies that for $0 \leq w^{\prime } < z$

  \begin{equation} \label{conditionof112} \min (y,h(w^{\prime }+s)) \oplus (w^{\prime }+s) \geq s. \end{equation}   (4.17)

Lemma 4.3, the inequality in (4.16), the inequality in (4.17) and Equation (4.15) imply (4.14). We have completed the proof.

Theorem 4.1. Let $s$ be a natural number such that

  \begin{equation} \label{conditionofs3} i \oplus s = i + s \text { for } i = 0,1,2,...,h(s) \end{equation}   (4.18)

and $h_ s(z) = h(z+s)$ for any $z \in Z_{\geq 0}$. Let $G_{h_ s}(\{ y,z\} )$ be the Grundy number of $CB(h_ s,y,z)$. Then $G_{h_ s}(\{ y,z\} )= (y \oplus (z+s))-s$ for any $y,z \in Z_{\geq 0}$ such that $y \leq h_ s(z)$. Let $y,z \in Z_{\geq 0}$ such that $y \leq h_ s(z)$. We prove by mathematical induction, and we assume that $G_{h_ s}(\{ v,w\} )= (v \oplus (w+s))-s$ for $v,w \in Z_{\geq 0}$ such that $v \leq y, w< z$ or $v < y, w \leq z$.

  $\displaystyle G_{h_ s}(\{ y,z\} )=\textit{mex}(\{ G_{h_ s}(\{ v,z\} ):v<y\} \cup \{ G_{h_ s}(\{ \min (y,h_ s(w)),w\} ):w < z\} )\nonumber $    
  $\displaystyle =\textit{mex}(\{ (v \oplus (z+s))-s :v<y\} \cup \{ (\min (y,h(w+s)) \oplus (w+s))-s :w< z \} )\nonumber $    
  $\displaystyle =\textit{mex}(\{ (v \oplus (z+s))-s :v<y\} \cup \{ (\min (y,h(w+s)) \oplus (w+s))-s :s \leq w+s < z+s\} )\nonumber $    
  $\displaystyle =\textit{mex}(\{ (v \oplus (z+s))-s :v<y\} \cup \{ (\min (y,h(w^{\prime })) \oplus w^{\prime })-s :s \leq w^{\prime } < z+s\} )\label{gsgrundy1}. $   (4.19)

By Lemma 4.5, $(\ref{gsgrundy1}) = (y \oplus (z+s))-s $, and hence we finish this proof.

A Necessary Condition for a Chocolate Bar to have the Grundy Number (y⊕(z+s))-s