1 Introduction

The original chocolate bar game [2] had a rectangular bar of chocolate with one bitter corner. Each player in turn breaks the bar in a straight line along the grooves and eats the piece he breaks off. The player who breaks the chocolate bar and eats to leave his opponent with the single bitter block (black block) is the winner.

The $4 \times 3$ rectangular chocolate bar in Figure 1.1 is equivalent to the game of NIM with a heap of 3 stones and a heap of 2 stones. Here, 3 is the number of grooves above and 2 is the number of grooves to the right of the bitter square. Since the Grundy number of the game of NIM with a heap of $3$ stones and a heap of $2$ stones is $3 \oplus 2$ , the Grundy number of the chocolate bar in Figure 1.1 is $3 \oplus 2$ .

In this paper, we consider step chocolate bars as in Figures 1.2, 1.3, 1.4,1.5,1.6, 1.7 and etc. In these cases, a vertical break can reduce the number of horizontal breaks. We can still think of the game as being played with heaps but now a move may change more than one heap.

Next, we define coordinates {y,z} for each chocolate. Let $y=m-1$ and $z=n-1$ , where $m$ is is the largest width of the chocolate and $n$ is the longest horizontal distance from the bitter part. (We use $x$ -coodinate later in this paper.)

The $y$ -coordinate and the $z$ -cooridinate of each step chocolate bar in Figures 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 are {3,13}, {4,9}, {2,9}, {5,5}, {3,11} and {2,14}. Here, the first number is the $y$ -coordinate and the second number is the $z$ -coordinate of each chocolate. For an example, the $y$ -coordinate and the $z$ -cooridinate of the chocolate bar in Figure 1.2 are 3 and 13 respectively.

If we caluculate the Grundy numbers of chocolate bars in Figures 1.2, 1.3 and 1.4, we have 14= $3 \oplus 13$ , 13= $4 \oplus 9$ and 11= $2 \oplus 9$ . (Here, we omit the calculation of Grundy numbers.)

If we caluculate the Grundy numbers of chocolate bars in Figures 1.5, 1.6 and 1.7, then we have $8 \neq 0=5\oplus 5$ , $13 \neq 8=3\oplus 11$ and $15 \neq 12=2\oplus 14$ . (Here, we omit the calculation of Grundy numbers.) Now we know that the Grundy number of some step chocolates are $y \oplus z$ , where $y$ and $z$ are coordinates of the chocolate, but the Grundy number of some step chocolates are not $y \oplus z$ .

When the width of chocolate bar is proportional to the distance from the bitter square and the constant of proportionality is even, the authors have already proved that the Grundy number of this chocolate bar is $y \oplus z$ , where $y,z$ are the coordinates of the chocolate bar. This result was published in a mathematics journal (Integers, Volume 15, 2015). Chocolates in Figures 1.2, 1.3 and 1.4 are examples of this type of chocolates.

On the other hand, if the constant of proportionality is odd, the Grundy number of this chocolate bar is not $y \oplus z$ . Chocolates in Figures 1, 1 and 1 are examples of this type of chocolates.

Therefore it is natural to look for a necessary and sufficient condition for chocolate bars to have the Grundy number that is equal to $y \oplus z$ , where $y$ and $z$ are coordinates of the chocolate.

There are other types of chocolate bar games, and one of the most well known is CHOMP. CHOMP is a game with a rectangular chocolate bar. The players take turns, and they choose one block and eat it together with those that are below it and to its right. The top left block is bitter and the players cannot eat this block. Although many people have studied this game, the winning strategy is yet to be discovered. For an overview of research of CHOMP, see [3].


{3,2}	{3,13}	{4,9}
Grundy number is 1= $3 \oplus 2$ .	Grundy number is 14= $3 \oplus 13$ .	Grundy number is 13= $4 \oplus 9$ .

{2,9}	{5,5}	{3,11}
Grundy number is 11= $2 \oplus 9$ .	Grundy number is $8 \neq 0=5\oplus 5$ .	Grundy number is $13 \neq 8=3\oplus 11$ .

{2,14}
Grundy number is $15 \neq 12=2\oplus 14$ .

Let $Z_{\geq 0}$ be the set of non-negative integers.

For completeness, we briefly review some necessary concepts in combinatorial game theory; see [4] or [5]for more details.

Definition 1.1. Let $x$ , $y$ be non-negative integers, and write them in base 2, so that $x = \sum _{i=0}^ n x_ i 2^ i$ and $y = \sum _{i=0}^ n y_ i 2^ i$ with $x_ i,y_ i \in \{ 0,1\}$ . We define the nim-sum $x \oplus y$ by

$\begin{equation} x \oplus y = \sum \limits _{i = 0}^ n {{w_ i}} {2^ i}, \end{equation}$

(1.1)

where $w_{i}=x_{i}+y_{i} \ (mod\ 2)$ .

Since chocolate bar games are impartial games without draws there will only be two outcome classes.

Definition 1.2.

$(a)$ $\mathcal{N}$ -positions, from which the next player can force a win, as long as he plays correctly at every stage.
$(b)$ $\mathcal{P}$ -positions, from which the previous player (the player who will play after the next player) can force a win, as long as he plays correctly at every stage.

Definition 1.3. The disjunctive sum of two games, denoted $\mathbf{G}+\mathbf{H}$ , is a super-game where a player may move either in $\mathbf{G}$ or in $\mathbf{H}$ , but not both.

For any position $\mathbf{p}$ of a game $\mathbf{G}$ , there is a set of positions that can be reached by making precisely one move in $\mathbf{G}$ , which we will denote by move $(\mathbf{p})$ .

Remark 1.1. As to the examples of move, please see Example 2.3.

Definition 1.5. (i) The minimum excluded value ( $\textit{mex}$ ) of a set, $S$ , of non-negative integers is the least non-negative integer which is not in S.
(ii) Each position $\mathbf{p}$ of a impartial game has an associated Grundy number, and we denoted it by $G(\mathbf{p})$ .
Grundy number is found recursively: $G(\mathbf{p}) = \textit{mex}\{ G(\mathbf{h}): \mathbf{h} \in move(\mathbf{p})\} .$

We present some lemmas for minimum excluded value $mex$ .

Lemma 1.1. Let $x \in Z_{\geq 0}$ and $y_ k \in Z_{\geq 0}$ for $k=1,2,...,n$ . Then Condition (i ) is true if and only if Condition (ii) is true.
(i) $x = \textit{mex}(\{ y_ k,k=1,2,...,n\} )$ .
(ii) $x \neq y_ k$ for any $k$ and for any $u \in Z_{\geq 0}$ such that $u < x$ there exists $k$ such that $u = y_ k$ . This is direct from Definition 1.5 (the definition of $mex$ ).

Lemma 1.2. Let $S$ be a set and $\{ 1,2,3,...,m-1\} \subset S$ . Then $\textit{mex}(S) \geq m$ . This is direct from the definition of $mex$ in Definition 1.5.

The power of the Sprague-Grundy theory for impartial games is contained in the next result.

Theorem 1.1. Let $\mathbf{G}$ and $\mathbf{H}$ be impartial games, and let $G_{\mathbf{G}}$ and $G_{\mathbf{H}}$ be Grundy numbers of $\mathbf{G}$ and $\mathbf{H}$ respectively. Then we have the following:
$(i)$ For any position $\mathbf{g}$ of $\mathbf{G}$ we have $G_{\mathbf{G}}(\mathbf{g})=0$ if and only if $\mathbf{g}$ is a $\mathcal{P}$ -position.
$(ii)$ The Grundy number of a position $\{ \mathbf{g},\mathbf{h}\}$ in the game $\mathbf{G}+\mathbf{H}$ is $G_{\mathbf{G}}(\mathbf{g})\oplus G_{\mathbf{H}}(\mathbf{h})$ . For a proof of this theorem, see [4].

Grundy Numbers of chocolate bar