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)

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

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)