Rational Heap Games

Abstract

We study variations of classical combinatorial games on two finite heaps of tokens, a.k.a. \emph{subtraction games}. Given non-negative integers $p_1,q_1,p_2,q_2$, where $p_1{q}_2>q_1{p}_2$, $p_1>0$ and $q_2>0$, two players alternate in removing $(m_1,m_2)\ne (0,0)$ tokens from the respective heaps, where the allowed ordered pairs of non-negative integers are given by a certain move set $(m_1,m_2)\in\M$. There is a restriction imposed on the allowed heap sizes $(X,Y)$, they must satisfy $X{q}_1\le Y{p}_1$ and $Y{p}_2\le X{q}_2$. A player who cannot move loses and the other player wins. For a certain restriction of these games, namely where each allowed move option $(m_1,m_2)$ is of the form $(s{p}_1+t{p}_2,s{q}_1+t{q}_2)$, for some ordered pair of non-negative integers $(s,t)\ne (0,0)$, we show that all games have equivalent outcomes via a certain surjective map to a canonical subtraction game. Other interests in our games are various interactions with classical combinatorial games such as \emph{Nim} and \emph{Wythoff Nim}.

16 pages, 7 figures