i-Mark: A new subtraction division game

详细信息    查看全文

• 作者：É ; ric Sopena^a ; ^b ; ¹ ; ^{eric.sopena@labri.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Combinatorial games ; Subtraction games ; Subtraction division games ; Sprague&ndash ; Grundy sequence ; Aperiodicity
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：9 May 2016
• 年：2016
• 卷：627
• 期：Complete
• 页码：90-101
• 全文大小：385 K

文摘

Given two finite sets of integers 16001808&_mathId=si1.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=30b97daafa21c1e91e78a22992c3ccde" title="Click to view the MathML source">S⊆N∖{0}$S\subseteq \mathbb{N}\setminus \{0\}$ and 16001808&_mathId=si2.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=3136f4808d7929e2868fbd21d5abe214" title="Click to view the MathML source">D⊆N∖{0,1}$D\subseteq \mathbb{N}\setminus \{0,1\}$, the impartial combinatorial game 16001808&_mathId=si3.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=d394395cfc36887c6d73686f026f94c7" title="Click to view the MathML source">i-Mark(S,D)$i\text{-<small-caps>Mark</small-caps>}(S,D)$ is played on a heap of tokens. From a heap of n   tokens, each player can move either to a heap of 16001808&_mathId=si4.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=cac4228a580e32430b01c9ea3c5ad4f8" title="Click to view the MathML source">n−s$n-s$ tokens for some 16001808&_mathId=si5.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=a879e659c11a0d014417eed922109eaf" title="Click to view the MathML source">s∈S$s\in S$, 16001808&_mathId=si6.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=eddf5265ead9ad8859e4fc02acb0ed8d" title="Click to view the MathML source">s≤n$s\le n$, or to a heap of 16001808&_mathId=si7.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=fabaf9a482e38b4519853ef4266b2c01" title="Click to view the MathML source">n/d$n/d$ tokens for some 16001808&_mathId=si396.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=67016a0b0e461e71c530f041ce56520f" title="Click to view the MathML source">d∈D$d\in D$ if d divides n. Such games can be considered as an integral variant of Mark-type games, introduced by Elwyn Berlekamp and Joe Buhler and studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of n   tokens to a heap of 16001808&_mathId=si9.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=0c5cb95948456a5a7372542aacb62561" title="Click to view the MathML source">⌊n/d⌋$\lfloor n/d\rfloor$ tokens for any 16001808&_mathId=si396.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=67016a0b0e461e71c530f041ce56520f" title="Click to view the MathML source">d∈D$d\in D$.

Under normal convention, it is observed that the Sprague–Grundy sequence of the game 16001808&_mathId=si3.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=d394395cfc36887c6d73686f026f94c7" title="Click to view the MathML source">i-Mark(S,D)$i\text{-<small-caps>Mark</small-caps>}(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 sequence 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 16001808&_mathId=si10.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=a167e16b60351b0a8c7d27e7626022a8" title="Click to view the MathML source">O(log⁡n)$O(\log n)$.

We also prove that under misère convention the outcome sequence of these games is purely periodic.