3.2 A Necessary Condition for a Chocolate Bar to have the Grundy Number $y \oplus z$

In Subsection 3.1, we proved that the Grundy number $G(\{ y,z\} ) = y \oplus z$ for $CB(h,y,z)$ when the function $h$ satisfies the condition $(a)$ in Definition 3.2.

In this subsection, we prove that the condition $(a)$ in Definition 3.2 is a necessary condition for $f$ to have the Grundy number $ y \oplus z$ for the chocolate bar $CB(f,y,z)$. Let $f$ be a monotonically increasing function of $Z_{\geq 0}$ into $Z_{\geq 0}$ that satisfies the following condition $(a)$.
$(a)$ Suppose that $G(\{ y,z\} )$ is the Grundy number of the chocolate bar $CB(f,y,z)$. Then,

  \begin{equation} G(\{ y,z\} ) = y \oplus z.\nonumber \end{equation}    

Throughout this subsection we assume that the function $f$ satisfies the condition $(a)$ of Definition 3.4, and we prove that this function $f$ satisfies the condition $(a)$ of Definition 3.2 using the following Lemma 3.9, Lemma 3.10 and Lemma 3.11.

Lemma 3.9. Let $y,z,y^{\prime } \in Z_{\geq 0}$ such that $y=f(z)$, $y^{\prime } \leq f(z+1)$ and $y < y^{\prime }$. Then, $G(\{ y,z+1\} ) < G(\{ y^{\prime },z+1\} )$.

Proof. Since $y=f(z)$, we have $f(w) \leq y < y^{\prime }$ for $w \leq z$. Therefore, $move_ f(\{ y^{\prime },z+1\} )= \{ \{ v,z+1 \} :v<y^{\prime } \} \cup \{ \{ \min (y^{\prime }, f(w)),w \} :w<z+1 \} $ $= \{ \{ v,z+1 \} :v<y^{\prime } \} \cup \{ \{ f(w),w \} :w<z+1 \} $ $=\{ \{ v,z+1\} : y \leq v < y^{\prime } \} \cup \{ \{ v,z+1 \} :v<y \} \cup \{ \{ f(w),w \} :w<z+1 \} $

$ =\{ \{ v,z+1\} : y \leq v < y^{\prime } \} \cup \{ \{ v,z+1 \} :v<y \} \cup \{ \{ \min (y, f(w)),w \} :w<z+1 \} $ $=\{ \{ v,z+1\} : y \leq v < y^{\prime } \} \cup move_ f(\{ y,z+1\} )$, where $v,w \in Z_{\ge 0}$.

  $\displaystyle \text { Therefore, } G(\{ y^{\prime },z+1\} ) \hspace{12cm} \nonumber $    
  $\displaystyle = \textit{mex}(\{ G(\{ v,z+1\} ):y \leq v < y^{\prime } \} \cup \{ G(\{ a,b\} ):\{ a,b\} \in move_ f(\{ y,z+1\} )\} \geq G(\{ y,z+1\} ).\hspace{0.8cm} \label{grundylqgrundy} $   (3.44)

Since $\{ y,z+1\} \in move_ f(\{ y^{\prime },z+1\} )$, $G(\{ y^{\prime },z+1\} ) \neq G(\{ y,z+1\} )$. Therefore, (3.44) implies $G(\{ y,z+1\} ) < G(\{ y^{\prime },z+1\} )$.

Lemma 3.10. For any $y,z \in Z_{\geq 0}$ such that $y \leq f(z)$, we have $\{ G(\{ \min (y,f(w)),w\} ):w<z\} = \{ y \oplus w:w < z\} $. Let $w \in Z_{\geq 0}$ such that $w< z$, and let

  \begin{equation} \label{2nbiggerywz} n = \lfloor log_2 \max (y,z) \rfloor +1. \end{equation}   (3.45)

Then, Equation (3.45) implies that $y \oplus w < y \oplus (z+2^ n) = G(\{ y,z+2^ n\} )$. By the definition of Grundy number, there exist $a,b \in Z_{\geq 0}$ such that $\{ a,b\} \in move_ f(\{ y,z+2^ n\} )$ and $G(\{ a,b\} )=y \oplus w$.
By the definition of $move_ f$, we have the following Equation (3.46) or Equation (3.47).

  \begin{equation} \label{bydefofmove1} G(\{ \min (y,f(w^{\prime })), w^{\prime } \} ) = y \oplus w \end{equation}   (3.46)

for $w^{\prime } \in Z_{\geq 0}$ with $w^{\prime } < z+2^ n$.

  \begin{equation} \label{bydefofmove2} y^{\prime } \oplus ( z+2^ n) = G(\{ y^{\prime }, z+2^ n\} ) = y \oplus w \end{equation}   (3.47)

for $y^{\prime } \in Z_{\geq 0}$ with $y^{\prime } < y$. Equation (3.47) contradicts Equation (3.45), and hence we have Equation (3.46).

If

  \begin{equation} \label{ifsentence} w^{\prime } \geq z, \end{equation}   (3.48)

then $f(w^{\prime }) \geq f(z) \geq y$. Hence,

  \begin{equation} \label{grundyyszp} G(\{ \min (y,f(w^{\prime })), w^{\prime } \} ) = G(\{ y,w^{\prime } \} ) = y \oplus w^{\prime }. \end{equation}   (3.49)

By Equations (3.46) and (3.49), we have

  \begin{equation} \label{leadcontra1} y \oplus w = y \oplus w^{\prime }. \end{equation}   (3.50)

Since $w^{\prime } < w$, Equation (3.50) leads to a contradiction. Therefore, the inequality in (3.48) is false, and we have $w^{\prime } < z$. Hence, Equation (3.46) implies that $\{ y \oplus w:w < z\} \subset \{ G(\{ \min (y,f(w)),w\} ):w<z\} $. The number of elements in $\{ y \oplus w:w < z\} $ is the same as the number of elements in $ \{ G(\{ \min (y,f(w)),w\} ):w<z\} $, and hence we have $\{ G(\{ \min (y,f(w)),w\} ):w<z\} = \{ y \oplus w:w < z\} $.

Lemma 3.11 Let

  \begin{equation} a= d \times 2^{i+1} + d_ i 2^ i + e-1 \nonumber \end{equation}    

for $d,e,i \in Z_{\geq 0} $, $d_ i \in \{ 0,1\} $, $e < 2^ i$ and $0 < d_ i 2^ i + e$.
If $c \times 2^{i+1} \leq f(a) < c \times 2^{i+1} + 2^ i$ for $c \in Z_{\geq 0}$, then $f(a+1) < c \times 2^{i+1} + 2^ i$. Let

  \begin{equation} \label{asnlemma1} f(a) = c \times 2^{i+1} + t \end{equation}   (3.51)

for $0 \leq t < 2^ i$. We suppose that

  \begin{equation} \label{aleadtocont} f(a+1) \geq c \times 2^{i+1} + 2^ i, \end{equation}   (3.52)

and we show that this leads to a contradiction.


Case $(i)$ If $d_ i = 1$, then
$G(\{ c \times 2^{i+1}+2^ i,a+1\} ) = (c \times 2^{i+1} + 2^ i) \oplus (d \times 2^{i+1} + d_ i 2^ i + e)$

  \begin{equation} \label{contradlemma35} = (c \oplus d) 2^{i+1} + e < (c \oplus d) 2^{i+1} + d_ i 2^ i + (t\oplus e) = G(\{ c \times 2^{i+1} + t, a +1\} ). \end{equation}   (3.53)

By Equation (3.51), the inequality in (3.52) and Lemma 3.9, we have $G(\{ c \times 2^{i+1} + t, a +1\} )< G(\{ c \times 2^{i+1}+2^ i,a+1\} )$, which contradicts Equation (3.53).
Case $(ii)$ If $d_ i = 0$, then $G(\{ c \times 2^{i+1}+2^ i,a+1\} ) = (c \times 2^{i+1} + 2^ i) \oplus (d \times 2^{i+1} + e)$
$ = (c \oplus d) 2^{i+1} + 2^ i + e > (c \oplus d) 2^{i+1} + 2^ i $. Note that $e > 0$, since $d_ i2^ i + e > 0$ and $d_ i = 0$.

Therefore, by the definition of Grundy number we have

  \begin{equation} \label{asnlemma2} (c \oplus d) 2^{i+1} + 2^ i \in \{ G(\{ p,q\} ):\{ p,q\} \in move_ f(\{ c \times 2^{i+1}+2^ i,a+1\} )\} . \end{equation}   (3.54)

$\{ G(\{ p,q\} ):\{ p,q\} \in move_ f(\{ c \times 2^{i+1}+2^ i,a+1\} )\} $

  $\displaystyle = \{ G(\{ v,d \times 2^{i+1}+e\} ):v = 0,1,2,...,c \times 2^{i+1}+2^ i-1\} \nonumber $    
  $\displaystyle \cup \{ G(\{ \min (c \times 2^{i+1}+2^ i,f(w)),w \} ):w = 0,1,2,...,d \times 2^{i+1}+e-1 \} . \label{atransgrundy} $   (3.55)

Note that $a=d \times 2^{i+1}+e-1$.

For $w \leq a$, we have $f(w) \leq f(a) = c\times 2^{i+1} + t$. Hence

  (3.55) $\displaystyle (\ref{atransgrundy}) = \{ G(\{ v,d \times 2^{i+1}+e\} ):v = 0,1,2,...,c \times 2^{i+1}+2^ i-1\} \nonumber $    
  $\displaystyle \cup \{ G(\{ \min (c \times 2^{i+1}+t,f(w)),w \} ):w = 0,1,2,...,d \times 2^{i+1}+e-1 \} .\label{lastofequation} $   (3.56)

Since $c \times 2^{i+1}+t=f(a)$ $\leq f(a+1)=f(d \times 2^{i+1}+e)$, Lemma 3.10 implies that $\{ G(\{ \min (c \times 2^{i+1}+t,f(w)),w \} ):w = 0,1,2,...,d \times 2^{i+1}+e-1 \} = \{ (c \times 2^{i+1}+t) \oplus w: w = 0,1,2,...,d \times 2^{i+1}+e-1 \} $. Therefore, by Definition 3.4

(3.56) $\displaystyle (\ref{lastofequation}) = \{ v \oplus (d \times 2^{i+1}+e): v = 0,1,2,...,c \times 2^{i+1}+2^ i-1\} \nonumber $    
  $\displaystyle \cup \{ (c \times 2^{i+1}+t) \oplus w: w = 0,1,2,...,d \times 2^{i+1}+e-1 \} \nonumber $    
  $\displaystyle = \{ (c \times 2^{i+1}+k)\oplus (d \times 2^{i+1}+e):k = 0,1,2,...,2^ i-1\} \label{agrundyse1} $   (3.57)
  $\displaystyle \cup \{ k \oplus (d \times 2^{i+1}+e):k = 0,1,2,...,c \times 2^{i+1}-1\} \label{agrundyse2} $   (3.58)
  $\displaystyle \cup \{ (c \times 2^{i+1}+t) \oplus (d \times 2^{i+1}+k):k = 0,1,2,...,e-1\} \label{agrundyse3} $   (3.59)
  $\displaystyle \cup \{ (c \times 2^{i+1}+t) \oplus k:k = 0,1,2,...,d \times 2^{i+1}-1 \} .\label{agrundyse4} $   (3.60)

Then we have the following statements $(i)$, $(ii)$, $(iii)$ and $(iv)$.
$(i)$ All the numbers in Set (3.57) are of the type $(c\oplus d)2^{i+1} + (k \oplus e)$, and hence this set does not contains $(c \oplus d) 2^{i+1} + 2^ i$. Note that $k,e < 2^ i$.
$(ii)$ The coefficients of $2^{i+1}$ of the numbers in Set (3.58) are not $c\oplus d$, and hence this set does not contains $(c \oplus d) 2^{i+1} + 2^ i$.
$(iii)$ All the numbers in Set (3.59) are of the type $(c\oplus d)2^{i+1} + (t \oplus k)$, and hence this set does not contains $(c \oplus d) 2^{i+1} + 2^ i$.
Note that $k \leq e-1 < 2^ i$ and $t < 2^ i$.
$(iv)$ The coefficients of $2^{i+1}$ of the numbers in Set (3.60) are not $c\oplus d$, and hence this set does not contains $(c \oplus d) 2^{i+1} + 2^ i$.
Statements $(i)$, $(ii)$, $(iii)$ and $(iv)$ contradict Relation (3.54). Therefore we conclude that the inequality in (3.52) is false.

Theorem 3.3. Suppose that the function $f$ satisfies the condition $(a)$ in Definition 3.4.
Then function $f$ satisfies the condition $(a)$ in Definition 3.2.

Proof. If $f$ does not satisfy the condition in Definition 3.2, then there exist $z,z^{\prime } \in Z_{\geq 0}$ and a natural number $j$ such that $z < z^{\prime }$,

  \begin{equation} \label{donotsatisfy1} \lfloor \frac{z}{2^ j}\rfloor = \lfloor \frac{z^{\prime }}{2^ j}\rfloor \end{equation}   (3.61)

and

  \begin{equation} \label{donotsatisfy2} \lfloor \frac{f(z)}{2^{j-1}}\rfloor < \lfloor \frac{f(z^{\prime })}{2^{j-1}}\rfloor . \end{equation}   (3.62)

By Equation (3.61), there exist $z_ k, z^{\prime }_ k \in Z_{\geq 0}$ for $k =0,1,2,...,n$ such that $ z=\sum \limits _{k = 0}^ n {{z_ k}} {2^ k}$ and $z^{\prime } = \sum \limits _{k = j}^ n {{z_ k}} {2^ k}+\sum \limits _{k = 0}^{j-1} {{z_ k^{\prime }}} {2^ k}$. By the inequality in (3.62), there exist $y_ k, y_ k^{\prime } \in Z_{\geq 0}$ for $k =0,1,2,...,n$ and a natural number $i \geq j-1$ such that $y_ i = 0 < 1 = y_ i^{\prime }$,

  \begin{equation} \label{atheoremforhf} f(\sum \limits _{k = 0}^ n {{z_ k}} {2^ k})= \sum \limits _{k = i+1}^{n} {{y_ k}} {2^ k} + y_ i \times 2^{i} + \sum \limits _{k = 0}^{i-1} {{y_ k}} {2^ k} \end{equation}   (3.63)

and

  \begin{equation} \label{atheoremforhf2} f(\sum \limits _{k = j}^ n {{z_ k}} {2^ k}+\sum \limits _{k = 0}^{j-1} {{z_ k^{\prime }}} {2^ k}) = \sum \limits _{k = i+1}^{n} {{y_ k}} {2^ k}+ y_ i^{\prime } \times 2^ i + \sum \limits _{k = 0}^{i-1} {{y_ k^{\prime }}} {2^ k}. \end{equation}   (3.64)

Let $c =\sum \limits _{k = i+1}^{n} {{y_ k}} {2^{k-(i+1)}} $. Then $c \times 2^{i+1}$ $= \sum \limits _{k = i+1}^{n} {{y_ k}} {2^ k}$. Hence Equations (3.63) and (3.64) imply that

  \begin{equation} \label{atheoremforhfp2} f(\sum \limits _{k = 0}^ n {{z_ k}} {2^ k})= c \times 2^{i+1} + 0 \times 2^{i} + \sum \limits _{k = 0}^{i-1} {{y_ k}} {2^ k} \end{equation}   (3.65)

and

  \begin{equation} \label{atheoremforhfp2b} f(\sum \limits _{k = j}^ n {{z_ k}} {2^ k}+\sum \limits _{k = 0}^{j-1} {{z_ k^{\prime }}} {2^ k}) = c \times 2^{i+1}+ 2^ i + \sum \limits _{k = 0}^{i-1} {{y_ k^{\prime }}} {2^ k}. \end{equation}   (3.66)

Let

  \begin{equation} \label{definitionofvaa} a = \max (\{ z: f(z) < c \times 2^{i+1} + 2^ i\} ) \end{equation}   (3.67)

and

  \begin{equation} \label{definitionofvab} b = \min (\{ z: f(z) \geq c \times 2^{i+1} + 2^ i\} ). \end{equation}   (3.68)

Then, $b = a+1$ follows directly from (3.67) and (3.68). Let $d =\sum \limits _{k = i+1}^{n} {{z_ k}} {2^{k-(i+1)}} $. Then, $d \times 2^{i+1}$ $= \sum \limits _{k = i+1}^{n} {{z_ k}} {2^ k}$. By (3.65),

$f(d \times 2^{i+1})$ $ \leq f(\sum \limits _{k = 0}^{n} {{z_ k}} {2^ k})$ $<c \times 2^{i+1}+2^ i$, and hence Equation (3.67) implies

  \begin{equation} \label{alargedm2} a \geq \sum \limits _{k = 0}^ n {{z_ k}} {2^ k} \geq d \times 2^{i+1}. \end{equation}   (3.69)

By $i+1 \geq j$, we have $(d+1) \times 2^{i+1} $ $=\sum \limits _{k = i+1}^{n} {{z_ k}} {2^ k}+2^{i+1} $ $ > \sum \limits _{k = j}^ n {{z_ k}} {2^ k}+\sum \limits _{k = 0}^{j-1} {{z_ k^{\prime }}} {2^ k}$.                                                                  

Hence Equations (3.68), (3.66) and the inequality in (3.69) implies that $(d+1) \times 2^{i+1} > b = a+1 > d \times 2^{i+1}$. Therefore, there exist $d_ i$ and $e$ such that $a+1 = d \times 2^{i+1} + d_ i2^ i + e$, $e < 2^ i$ and $0<d_ i 2^ i + e$.

By Equation (3.65) and the inequality in (3.69), we have

  \begin{equation} \label{finalcondition1} f(a) \geq f(\sum \limits _{k = 0}^ n {{z_ k}} {2^ k}) \geq c \times 2^{i+1}. \end{equation}   (3.70)

Equation (3,67) implies

  \begin{equation} \label{finalcondition2} f(a) < c \times 2^{i+1} + 2^ i \end{equation}   (3.71)

and

  \begin{equation} \label{finalcondition3} f(a+1) \geq c \times 2^{i+1} + 2^ i. \end{equation}   (3.72)

Inequalities (3.70), (3.71) and (3.72) contradict the result of Lemma 3.11, and hence that $f$ satisfies the condition in Definition 3.1. By Theorem 3.3, the condition $(a)$ in Definition 3.1 is a necessary condition for $CB(f,y,z)$ to have the Grundy number $G(\{ y,z\} )=y \oplus z$.

A Chocolate Game CB(fs,y,z) whose Grundy number is Gfs({y,z})=(y⊕(z+s))-s for a fixed natural number s