{
  "id": "1108.1239",
  "version": "v2",
  "published": "2011-08-05T02:18:30.000Z",
  "updated": "2011-08-09T05:41:57.000Z",
  "title": "Winning strategies for aperiodic subtraction games",
  "authors": [
    "Alan Guo"
  ],
  "comment": "6 pages, no figuress, added references, fixed typos, made proofs more efficient",
  "categories": [
    "math.CO"
  ],
  "abstract": "We provide a winning strategy for sums of games of MARK-t, an impartial game played on the 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 solves a problem posed by Aviezri Fraenkel. In addition, we characterize the P-positions and N-positions for the game in mis\\`ere play.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-08-09T05:41:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "91A46",
      "91A05",
      "68Q25"
    ],
    "keywords": [
      "aperiodic subtraction games",
      "winning strategy",
      "quadratic time",
      "sprague-grundy values",
      "aviezri fraenkel"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1108.1239G"
    }
  }
}