i-\textsc{Mark}: a new subtraction division game

DOI10.1016/J.TCS.2016.03.002MaRDI QIDQ265084zbMATH OpenOpenAlexFDO

Authors Éric Sopena

Publication date 1 April 2016

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

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

zbMATH Keywords

aperiodicitycombinatorial gamesSprague-Grundy sequencesubtraction division gamessubtraction games

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Combinatorial games (91A46)

Abstract: Given two finite sets of integers $SsubseteqNNNsetminus0$ and $DsubseteqNNNsetminus0,1$,the impartial combinatorial game $IMARK(S,D)$ is played on a heap of tokens. From a heap of $n$ tokens, each player can moveeither to a heap of $n-s$ tokens for some $sinS$, or to a heap of $n/d$ tokensfor some $dinD$ if $d$ divides $n$.Such games can be considered as an integral variant of MARK-type games, introduced by Elwyn Berlekamp and Joe Buhlerand studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of $n$ tokensto a heap of $lfloorn/dfloor$ tokens for any $dinD$.Under normal convention, it is observed that the Sprague-Grundy sequence of the game $IMARK(S,D)$ is aperiodic for any sets $S$ and $D$.However, we prove that, in many cases, this sequence is almost periodic and that the set of winning positions is periodic.Moreover, in all these cases, the Sprague-Grundy value of a heap of $n$ tokens can be computed in time $O(logn)$.We also prove that, under mis`ere convention, the outcome sequence of these games is purely periodic.

Recommendations

• Some \(i\)-\textsc{Mark} games
• Winning strategies for aperiodic subtraction games
• Partizan octal games: Partizan subtraction games
• Faster evaluation of subtraction games
• scientific article; zbMATH DE number 1187950

Cites work

• Aperiodic subtraction games
• Combinatorial game theory
• scientific article; zbMATH DE number 5145315 (Why is no real title available?)
• The On-Line Encyclopedia of Integer Sequences
• The vile, dopey, evil and odious game players
• Winning strategies for aperiodic subtraction games
• Winning ways for your mathematical plays. Vol. 1.

Cited in

(3)

• Some \(i\)-\textsc{Mark} games
• A convergence technique for the game i-MARK
• Winning strategies for aperiodic subtraction games

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: \(i\)-\textsc{Mark}: a new subtraction division game

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