Maximum Nim and Chocolate Bar Games

Discrete and Computational Geometry, Graphs, and Games

Abstract

The authors studied maximum Nim wherein each player can remove at most $f(m)$ stones from a pile of $m$ stones, where $f(m)= \left\lceil \frac{m}{d} \right\rceil $ or $f(m)= \left\lfloor \frac{m+1}{d}\right\rfloor $ with a positive number $d$ that is larger than 1, and present function $h_{d}$ such that $\mathcal{G}(h_{d}(x)) = \mathcal{G}(x)$, where $\mathcal{G}(x)$ is the Grundy number of the pile of $x$ stones. The authors apply function $h_{d}$ to the study of chocolate bar games, wherein two players take turns and cut a chocolate bar in a straight line and eat the pieces. These games can be considered the sum of two maximum Nim with a restriction on the size of the chocolate bar that can be eaten by the players. Therefore, using $h_{d}$, the authors devise formulas to calculate the winning position of the previous player for a rectangular chocolate bar game with a restriction on the size of the chocolate bar piece to be eaten. In addition, the authors present conjectures about rectangular chocolate bar games with some missing parts.