Grundy Number of chocolate games

In this section we study chocolate games using Grundy Number.
First we define Grundy number for the Chocolate that satisfy the inequality $ky \leq z$ , where $k$ is a natural number.

Definition 4.1   Let $k$ be a natural number. For $x,y,z \in Z_{\ge 0}$ we define $movek(\{x,y,z\})=\{\{u,y,z \};u<x \} \cup \{\{x,v,z \};v<y \} \cup \{ \{x,\min(y, \lfloor w/k \rfloor ),w \};w<z \}$ , where $u,v,w \in Z_{\ge 0}$ .

$movek(\{x,y,z\})$ is the set of state that can be reached from the state $\{x,y,z\}$ directly.

We define the function $Mex(A)$ .

 

Definition 4.2   We define function $Mex(A)$ to be the least nonnegative integer not in the set $A$ .

Example 4.1   $Mex({0,1,4,5,6 })=2$ , $Mex( {1,4,5,6 })=0$ .

Next we define Grundy Number.

Definition 4.3   Let $Gk({0,0,0}) = 0$ . For a state $\{x,y,z\}$ we define Grundy Number recursively by
$Gk(\{x,y,z\})= Mex(Gk(\{u,v,w\});\{u,v,w\} \in movek(\{x,y,z\}))$ .

For the detailed theory of Grundy Number see [2].

Theorem 4.1   In chocolate games a state is an L-state of the game if and only if the Grundy number of the state is 0 .

This is a well known fact of Grundy Number. For a proof see [2]. Grundy Number is an effective tool to calculate L-states in combinatorial games, since by Theorem 4.1 we calculate L-states using Grundy Number .