Superpolynomial period lengths of the winning positions in the subtraction game

István Miklós () and Logan Post ()
Additional contact information
István Miklós: HUN-REN Rényi Institute
Logan Post: Budapest Semesters in Mathematics

International Journal of Game Theory, 2024, vol. 53, issue 4, No 10, 1275-1313

Abstract: Abstract Given a finite set of positive integers, A, and starting with a heap of n chips, Alice and Bob alternate turns and on each turn a player chooses $$x\in A$$ x ∈ A with x less than or equal to the current number of chips and subtract x chips from the heap. The game terminates when the current number of chips becomes smaller than $$\min \{A\}$$ min { A } and no moves are possible. The player who makes the last move is the winner. We define $$w^A(n)$$ w A ( n ) to be 1 if Alice has a winning strategy with a starting heap of n chips and 0 if Bob has a winning strategy. By the Pigeonhole Principle, $$w^A(n)$$ w A ( n ) becomes periodic, and it is easy to see that the period length is at most an exponential function of $$\max \{A\}$$ max { A } . The typical period length is a linear function of $$\max \{A\}$$ max { A } , and it is a long time open question if exponential period length is possible. We consider a slight modification of this game by introducing an iitial seed S that tells for the few initial numbers of chips whether the current or the opposite player is the winner, and the game ends when the first such position is achieved. In this paper we show that the initial seed cannot change the period length of $$w^A(n)$$ w A ( n ) if the size of A is 1 or 2, but it can change the period length with $$|A|\ge 3$$ | A | ≥ 3 . Further, we exhibit a class of sets A of size 3 and corresponding initial seeds such that the period length becomes a superpolynomial function of $$\max \{A\}$$ max { A } .

Keywords: Combinatorial games; Subtraction game; Superpolynomial period length; 91A46 (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-024-00911-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:53:y:2024:i:4:d:10.1007_s00182-024-00911-5

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-024-00911-5

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().