Heap games, numeration systems and sequences (Q1293425): Difference between revisions

This is a well-commented analysis of the following heap game (i.e., Nim-like game), depending on a pair of positive integers \((s,t)\): There are two heaps with (finitely many) tokens. Two players alternately remove tokens, either an arbitrary number from one of the heaps, or \(k\) tokens from one and \(l\) from the other heap, provided \( 0 < k \leq l < sk+t \). The player taking the last token wins. A strategy is described by a sequence \((A_n,B_n)\) of winning positions (i.e., the sizes of the heaps to be left for the opponent). While in the previously studied cases -- that are \((1,1)\) (Wythoff's game) and \((1,t)\) -- there are two (real) numbers \(\alpha\) and \(\beta\) such that the (winning) strategy has a (spectral) expression by \( A_n = \lfloor n\alpha \rfloor \) and \( B_n = \lfloor n\beta \rfloor \), this approach is shown to be impossible in the general case. Nevertheless the strategy is of polynomial (even linear) complexity (in the size of the input data, i.e., the \(\log \) of the heap size). It can be characterized using the expansion of integers with respect to an (increasing) recursive sequence of base (nodal) numbers: The \(A_n\) are those integers whose expansion ends on an even number of 0's, while \(B_n\) is the left shift (by one digit) of \(A_n\). In addition, an alternative characterization of the pairs \((A_n,B_n)\) is given.