Abstract | ||
---|---|---|
We provide a winning strategy for sums of games of Mark-t, an impartial game played on nonnegative integers where each move consists of subtraction by an integer between 1 and t−1 inclusive, or division by t, rounding down when necessary. Our algorithm computes the Sprague–Grundy values for arbitrary n in quadratic time. This addresses one of the directions of further study proposed by Aviezri Fraenkel. In addition, we characterize the P-positions and N-positions for the game in misère play. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.tcs.2011.11.025 | Theoretical Computer Science |
Keywords | Field | DocType |
Combinatorial games,Subtraction games,Complexity,Aperiodicity | Integer,Combinatorial game theory,Discrete mathematics,Combinatorics,Rounding,Time complexity,Aperiodic graph,Subtraction,Mathematics | Journal |
Volume | ISSN | Citations |
421 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 1 | 1 |