Grundy Numbers of Impartial Chocolate Bar Games


Chocolate bar games are variants of the CHOMP game in which the goal is to leave your opponent with the single bitter part of the chocolate. The original chocolate bar game [2] consists of a rectangular bar of chocolate with one bitter corner. Since the horizontal and vertical grooves are independent, an rectangular chocolate bar is equivalent to the game of NIM with a heap of $m-1$ stones and a heap of $n-1$ stones. Since the Grundy number of the game of NIM with a heap of $m-1$ stones and a heap of $n-1$ stones is $(m-1) \oplus (n-1)$, the Grundy number of this nbym rectangular bar is $(m-1) \oplus (n-1)$.

In this paper, we investigate step chocolate bars whose widths are determined by a fixed function of the horizontal distance from the bitter square.

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 $(m-1) \oplus (n-1)$, where $m$ is is the largest width of the chocolate and $n$ is the longest horizontal distance from the bitter part. This result was published in a mathematics journal (Integers, Volume 15, 2015).

On the other hand, if the constant of proportionality is odd, the Grundy number of this chocolate bar is not $(m-1) \oplus (n-1)$.

Therefore, it is natural to look for a necessary and sufficient condition for chocolate bars to have the Grundy number that is equal to $(m-1) \oplus (n-1)$, where $m$ is is the largest width of the chocolate and $n$ is the longest horizontal distance from the bitter part.

In the first part of the present paper, the authors present this necessary and sufficient condition.

Next, we modified the condition that the Grundy number that is equal to $(m-1) \oplus (n-1)$, and we studied a necessary and sufficient condition for chocolate bars to have Grundy number that is equal to $((m-1) \oplus (n-1+s))-s$, where $m$ is is the largest width of the chocolate and $n$ is the longest horizontal distance from the bitter part. We present this necessary and sufficient condition in the second part of this paper.