Heap games, numeration systems and sequences

DOI10.1007/BF01608532MaRDI QIDQ1293425zbMATH OpenOpenAlexFDO

Authors Aviezri S. Fraenkel

Publication date 20 August 2000

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9809074

zbMATH Keywords

heap gamesNim Wythoff's gamenumber systemssuccinct gamestree games

Mathematics Subject Classification ID

Other number representations (11A67) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Combinatorial games (91A46)

Abstract: We propose and analyse a 2-parameter family of 2-player games on two heaps of tokens, and present a strategy based on a class of sequences. The strategy looks easy, but is actually hard. A class of exotic numeration systems is then used, which enables us to decide whether the family has an efficient strategy or not. We introduce yet another class of sequences, and demonstrate its equivalence with the class of sequences defined for the strategy of our games.

Review text

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.

Recommendations

• A new heap game
• On Frankel's N-heap Wythoff's conjectures
• Nimlike games with generalized bases
• Nim games with arbitrary periodic moving orders

Cites work

• A linear algorithm for nonhomogeneous spectra of numbers
• A note on periodicity in some octal games
• How to Beat Your Wythoff Games' Opponent on Three Fronts
• scientific article; zbMATH DE number 3124339 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 3521877 (Why is no real title available?)
• scientific article; zbMATH DE number 3236819 (Why is no real title available?)
• scientific article; zbMATH DE number 3397597 (Why is no real title available?)
• scientific article; zbMATH DE number 3084373 (Why is no real title available?)
• Nonhomogeneous spectra of numbers
• On the complexity of some two-person perfect-information games
• Spectra of Numbers
• Systems of Numeration

Cited in

(29)

• Cubic pisot unit combinatorial games
• Geometrical extensions of Wythoff's game
• Recent results and questions in combinatorial game complexities
• A new heap game
• Arrays, numeration systems and Frankenstein games
• On variants of vertex geography on undirected graphs
• On tame, pet, domestic, and miserable impartial games
• Multi-player Wythoff's game and its variants
• Sumsets associated with Wythoff sequences and Fibonacci numbers
• Sumsets associated with Beatty sequences
• Adjoining to (K,s,t)-Wythoff's game its P-generators as moves
• Extensions of the combinatorial game \(( K , t )\)-Wythoff
• Variants of (s, t)-Wythoff's game
• Combinatorial structure and sumsets associated with Beatty sequences generated by powers of the golden ratio
• A morphic approach to combinatorial games: the Tribonacci case
• General restriction of (s,t)-Wythoff's game
• Two variants of Wythoff's game preserving its P-positions
• Adjoining to \((s,t)\)-Wythoff's game its \(P\)-positions as moves
• General restrictions of Wythoff-like games
• Deciding game invariance
• A class of extensions of restricted (\(s\), \(t\))-Wythoff's game
• \(a\)-Wythoff's game with \(n\) players
• Variants of Wythoff game with terminal positions or blocking maneuvers
• Automatic proofs in combinatorial game theory
• Proof of Irvine's conjecture via mechanized guessing
• Polynomial time winning strategies for three variants of \((s,t)\)-Wythoff's game
• A two-parameter family of an extension of Beatty sequences
• Extensions and restrictions of Wythoff's game preserving its \(\mathcal P\) positions
• Invariant games

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Heap games, numeration systems and sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1293425)