To divide chocolates into two parts.

Example 4.2   The chocolate game in Fig. 4.1 can be divided into two parts. See Fig. 4.2 and 4.3.

$y\leq \lfloor z/2 \rfloor$

Figure 4.1  

The left part of chocolate in Fig. 4.1.

Figure 4.2  

The right part of chocolate in Fig. 4.1.

Figure 4.3  

Similarly we can divide chocolates into two parts.

Definition 4.4   We divide the chocolate with the inequality $y\leq \left\lfloor \frac{z}{k} \right\rfloor$ into two parts, and we call these two parts the left part and the right part of the chocolate.

Example 4.3   This is an example of the division of the chocolate with the inequality $y\leq \left\lfloor \frac{z}{4} \right\rfloor$ into two parts.

$y\leq \left\lfloor \frac{z}{4} \right\rfloor$

Figure 4.4  

For the chocolate in Fig.4.4 the left part and the right part are the chocolates in Fig.4.5 and Fig.4.6.

The left part of chocolate in Fig. 4.4.

Figure 4.5  

The right part of chocolate in Fig. 4.4.

Figure 4.6  

We study Grundy numbers of the left part and the right part of the chocolate with the inequality $y\leq \left\lfloor \frac{z}{k} \right\rfloor$ . First we define $movekL$ and $movekR$ for the left part and the right part.

Definition 4.5   We define $movekL$ for the left part of the chocolate with the inequality $y\leq \left\lfloor \frac{z}{k} \right\rfloor$ .
For $x \in Z_{\ge 0}$ we define $movekL(\{x\})= \{\{u \};0 \leq u<x \}$ , where $u \in Z_{\ge 0}$ .

Definition 4.6   We define $movekR$ for the left part of the chocolate with the inequality $y\leq \left\lfloor \frac{z}{k} \right\rfloor$ .
For $y,z \in Z_{\ge 0}$ we define $movekR(\{y,z\})= \{\{v,z \};0 \leq v<y \} \cup \{ \{\min(y, \lfloor w/k \rfloor ),w \};0\leq w<z \}$ , where $v,w \in Z_{\ge 0}$ .

Next we define Grundy Numbers $GkL$ , $GkR$ for these two chocolates.

Definition 4.7   Let $GkL({0}) = 0$ . For a state $\{x\}$ we define Grundy Number recursively by $GkL(\{x\})= Mex(GkL(\{u\});\{u\} \in movekL(\{x\}))$ .

The Grundy number defined in Definition 4.5 is the same as the set of non-negative integers.

Definition 4.8   Let $GkR({0,0}) = 0$ . For a state $\{y,z\}$ we define Grundy Number recursively by
$GkR(\{y,z\})= Mex(GkR(\{v,w\});\{v,w\} \in movekR(\{y,z\}))$ .

We need the following theorem to study the sum of two games.

Theorem 4.2   Let $G,H$ be Grundy Numbers of two combinatorial games. Then the Grundy Number of the sum of these games is $G\oplus H$ .

This is a well known theorem of combinatorial games. See [2].

Lemma 4.1   $Gk(\{x,y,z\})=GkL(\{x\})\oplus GkR(\{y,z\})$ .

Proof   Since the chocolate game is the sum of its left part and the right part, this is direct from Theorem 4.2.

Lemma 4.2   $G2R(\{y,z\})=y\oplus z$ .

Proof   By Theorem 2.6, Theorem 4.1 and Lemma 4.1
$G2(\{x,y,z\})=G2L(\{x\})\oplus G2R(\{y,z\})=0$ if and only if $x\oplus y\oplus z= 0$ . It is clear that $G2L(\{x\})=x$ , and hence we have $G2R(\{y,z\})=y\oplus z$ .