التفاصيل البيبلوغرافية
| العنوان: |
Superpolynomial period lengths of the winning positions in the subtraction game: Superpolynomial period lengths...: I. Miklós, L. Post. |
| المؤلفون: |
Miklós, István1,2 (AUTHOR) miklos.istvan@renyi.hun-ren.hu, Post, Logan3,4 (AUTHOR) loganpost9@gmail.com |
| المصدر: |
International Journal of Game Theory. Dec2024, Vol. 53 Issue 4, p1275-1313. 39p. |
| مصطلحات موضوعية: |
EXPONENTIAL functions, OPEN-ended questions, INTEGERS, SEEDS, GAMES |
| مستخلص: |
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 ∈ 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 } and no moves are possible. The player who makes the last move is the winner. We define 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) becomes periodic, and it is easy to see that the period length is at most an exponential function of max { A } . The typical period length is a linear function of 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) if the size of A is 1 or 2, but it can change the period length with | 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 } . [ABSTRACT FROM AUTHOR] |
|
Copyright of International Journal of Game Theory is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |