{
  "id": "0901.4683",
  "version": "v2",
  "published": "2009-01-29T14:06:24.000Z",
  "updated": "2010-05-23T21:39:18.000Z",
  "title": "Restrictions of $m$-Wythoff Nim and $p$-complementary Beatty Sequences",
  "authors": [
    "Urban Larsson"
  ],
  "comment": "22 pages, 2 figures, Games of No Chance 4, Appendix by Aviezri Fraenkel",
  "categories": [
    "math.CO"
  ],
  "abstract": "Fix a positive integer $m$. The game of \\emph{$m$-Wythoff Nim} (A.S. Fraenkel, 1982) is a well-known extension of \\emph{Wythoff Nim}, a.k.a 'Corner the Queen'. Its set of $P$-positions may be represented by a pair of increasing sequences of non-negative integers. It is well-known that these sequences are so-called \\emph{complementary homogeneous} \\emph{Beatty sequences}, that is they satisfy Beatty's theorem. For a positive integer $p$, we generalize the solution of $m$-Wythoff Nim to a pair of \\emph{$p$-complementary}---each positive integer occurs exactly $p$ times---homogeneous Beatty sequences $a = (a_n)_{n\\in \\M}$ and $b = (b_n)_{n\\in \\M}$, which, for all $n$, satisfies $b_n - a_n = mn$. By the latter property, we show that $a$ and $b$ are unique among \\emph{all} pairs of non-decreasing $p$-complementary sequences. We prove that such pairs can be partitioned into $p$ pairs of complementary Beatty sequences. Our main results are that $\\{\\{a_n,b_n\\}\\mid n\\in \\M\\}$ represents the solution to three new '$p$-restrictions' of $m$-Wythoff Nim---of which one has a \\emph{blocking maneuver} on the \\emph{rook-type} options. C. Kimberling has shown that the solution of Wythoff Nim satisfies the \\emph{complementary equation} $x_{x_n}=y_n - 1$. We generalize this formula to a certain '$p$-complementary equation' satisfied by our pair $a$ and $b$. We also show that one may obtain our new pair of sequences by three so-called \\emph{Minimal EXclusive} algorithms. We conclude with an Appendix by Aviezri Fraenkel.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-05-23T21:39:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "91A46"
    ],
    "keywords": [
      "complementary beatty sequences",
      "restrictions",
      "positive integer",
      "wythoff nim satisfies",
      "satisfy beattys theorem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0901.4683L"
    }
  }
}