Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture

DOI10.1016/J.TCS.2010.11.015zbMATH Open1237.91062arXiv1005.4162OpenAlexW2071891973WikidataQ123220540 ScholiaQ123220540MaRDI QIDQ627170FDOQ627170

Authors: Urban Larsson, Aviezri S. Fraenkel, Peter Hegarty 

Publication date: 21 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We prove a recent conjecture of Duch^ene and Rigo, stating that every complementary pair of homogeneous Beatty sequences represents the solution to an emph{invariant} impartial game. Here invariance means that each available move in a game can be played anywhere inside the game-board. In fact, we establish such a result for a wider class of pairs of complementary sequences, and in the process generalize the notion of a emph{subtraction game}. Given a pair of complementary sequences $(a_n)$ and $(b_n)$ of positive integers, we define a game $G$ by setting $a_n,b_n$ as invariant moves. We then introduce the invariant game $G^{s}tar$, whose moves are all non-zero $P$-positions of $G$. Provided the set of non-zero $P$-positions of $G^{s}tar$ equals $a_n,b_n$, this emph{is} the desired invariant game. We give sufficient conditions on the initial pair of sequences for this 'duality' to hold.

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

Recommendations

• Invariant games
• Nonhomogeneous Beatty sequences leading to invariant games
• Beating Your Fractional Beatty Game Opponent and: What’s the Question to Your Answer?
• Deciding game invariance
• The \(\star\)-operator and invariant subtraction games

zbMATH Keywords

impartial gameBeatty sequencesuperadditivitycomplementary sequencesinvariant game

Mathematics Subject Classification ID

Special sequences and polynomials (11B83) Combinatorial games (91A46)

Cites Work

• On the complexity of some two-person perfect-information games
• Restrictions of $m$-Wythoff Nim and $p$-complementary Beatty Sequences
• Wythoff games, continued fractions, cedar trees and Fibonacci searches
• The Rat game and the Mouse game
• The \(\star\)-operator and invariant subtraction games
• A generalized diagonal Wythoff Nim
• Invariant games
• The Bracket Function and Complementary Sets of Integers
• Theory of annihilation games. I

Cited In (12)

• Invariant games
• Subtraction games in more than one dimension
• Nonhomogeneous Beatty sequences leading to invariant games
• From combinatorial games to shape-symmetric morphisms
• Rulesets for Beatty games
• Wythoff partizan subtraction
• Simplicial complexes are game complexes
• Deciding game invariance
• Self-similarity of \(\mathcal{P}\)-positions of \((2n+1)\)-dimensional Wythoff's game
• From heaps of matches to the limits of computability
• The \(\star\)-operator and invariant subtraction games
• Patterns in the generalized Fibonacci word, applied to games

This page was built for publication: Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture

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