i-Mark: A new subtraction division game

详细信息    查看全文

• 作者：&Eacute ; 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 an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si1.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=30b97daafa21c1e91e78a22992c3ccde" title="Click to view the MathML source">S⊆N∖{0}an>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">S⊆athvariant="double-struck">N∖alse">{0alse">}ath>an>an>an> and an id="mmlsi2" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si2.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=3136f4808d7929e2868fbd21d5abe214" title="Click to view the MathML source">D⊆N∖{0,1}an>an class="mathContainer hidden">an class="mathCode">ath altimg="si2.gif" overflow="scroll">D⊆athvariant="double-struck">N∖alse">{0,1alse">}ath>an>an>an>, the impartial combinatorial game an id="mmlsi3" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si3.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=d394395cfc36887c6d73686f026f94c7" title="Click to view the MathML source">i-Mark(S,D)an>an class="mathContainer hidden">an class="mathCode">ath altimg="si3.gif" overflow="scroll">i-all-caps>Markall-caps>alse">(S,Dalse">)ath>an>an>an> is played on a heap of tokens. From a heap of n   tokens, each player can move either to a heap of an id="mmlsi4" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si4.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=cac4228a580e32430b01c9ea3c5ad4f8" title="Click to view the MathML source">n−san>an class="mathContainer hidden">an class="mathCode">ath altimg="si4.gif" overflow="scroll">n−sath>an>an>an> tokens for some an id="mmlsi5" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si5.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=a879e659c11a0d014417eed922109eaf" title="Click to view the MathML source">s∈San>an class="mathContainer hidden">an class="mathCode">ath altimg="si5.gif" overflow="scroll">s∈Sath>an>an>an>, an id="mmlsi6" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si6.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=eddf5265ead9ad8859e4fc02acb0ed8d" title="Click to view the MathML source">s≤nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si6.gif" overflow="scroll">s≤nath>an>an>an>, or to a heap of an id="mmlsi7" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si7.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=fabaf9a482e38b4519853ef4266b2c01" title="Click to view the MathML source">n/dan>an class="mathContainer hidden">an class="mathCode">ath altimg="si7.gif" overflow="scroll">nalse">/dath>an>an>an> tokens for some an id="mmlsi396" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si396.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=67016a0b0e461e71c530f041ce56520f" title="Click to view the MathML source">d∈Dan>an class="mathContainer hidden">an class="mathCode">ath altimg="si396.gif" overflow="scroll">d∈Dath>an>an>an> if d divides n. Such games can be considered as an integral variant of an class="smallcaps">Markan>-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 an id="mmlsi9" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si9.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=0c5cb95948456a5a7372542aacb62561" title="Click to view the MathML source">⌊n/d⌋an>an class="mathContainer hidden">an class="mathCode">ath altimg="si9.gif" overflow="scroll">alse">⌊nalse">/dalse">⌋ath>an>an>an> tokens for any an id="mmlsi396" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si396.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=67016a0b0e461e71c530f041ce56520f" title="Click to view the MathML source">d∈Dan>an class="mathContainer hidden">an class="mathCode">ath altimg="si396.gif" overflow="scroll">d∈Dath>an>an>an>.

Under normal convention, it is observed that the Sprague–Grundy sequence of the game an id="mmlsi3" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si3.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=d394395cfc36887c6d73686f026f94c7" title="Click to view the MathML source">i-Mark(S,D)an>an class="mathContainer hidden">an class="mathCode">ath altimg="si3.gif" overflow="scroll">i-all-caps>Markall-caps>alse">(S,Dalse">)ath>an>an>an> 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 an id="mmlsi10" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001808&_mathId=si10.gif&_user=111111111&_pii=S0304397516001808&_rdoc=1&_issn=03043975&md5=a167e16b60351b0a8c7d27e7626022a8" title="Click to view the MathML source">O(log⁡n)an>an class="mathContainer hidden">an class="mathCode">ath altimg="si10.gif" overflow="scroll">Oalse">(athvariant="normal">log⁡nalse">)ath>an>an>an>.

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