A ruler regularity in hexadecimal games
Jeff P. Grossman, Richard J. Nowakowski · 2015
An important problem in the theory of impartial games is to determine the regularities of their nim-sequences. Subtraction games have periodic nim-sequences and those of octal games are conjectured to be periodic, but the possible regularities of the nim-sequence of a hexadecimal game are unknown. Periodic and arithmetic periodic nim-sequences have been discovered but other patterns also exist. We present an infinite set of hexadecimal games, based on the game 0.2048 , that exhibit a regularity—ruler regularity—not yet reported or codified. A taking-and-breaking game [Albert et al. 2007; Berlekamp et al. 2001] is an impartial combinatorial game, played with heaps of beans on a table. A move for either player consists of choosing a heap, removing a certain number of beans from the heap, and then possibly splitting the remainder into several heaps; the winner is the player making the last move. For example, both Grundy’s Game (choose a heap and split it into two unequal heaps) and Couples-Are-Forever (choose a heap with at least three beans and split it into two) are taking-and-breaking games with very simple rules, however neither has been solved. We present an overview of the required theory of impartial games. The reader can consult the references above for a more in-depth grounding in the theory of, and for more details about, subtraction and octal games.