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

number systemstree gamesheap gamesNim Wythoff's gamesuccinct games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Other number representations (11A67) 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.

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

• 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?)
• 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
• Nonhomogeneous spectra of numbers
• On the complexity of some two-person perfect-information games
• Spectra of Numbers
• Systems of Numeration

Cited in

(26)

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

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)