{
  "id": "2311.03257",
  "version": "v1",
  "published": "2023-11-06T16:41:26.000Z",
  "updated": "2023-11-06T16:41:26.000Z",
  "title": "GM-rule and its applications to impartial games",
  "authors": [
    "Vladimir Gurvich",
    "Mariya Naumova"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given integer $n \\geq 1, \\ell \\geq 2$, and vector $x = (x_1, \\ldots, x_n)$ that has an entry which is a multiple of $\\ell$ and such that $x_1 \\leq \\ldots \\leq x_n$, the GM-rule is defined as follows: Keep the rightmost minimal entry $x_i$ of $x$, which is a multiple of $\\ell$ and reduce the remaining $n-1$ entries of $x$ by~1. We will call such $i$ the {\\em pivot} and $x_i$ the {\\em pivotal entry}. The GM-rule respects monotonicity of the entries. It uniquely determines a GM-move $x^0 \\to x^1$ and an infinite GM-sequence $S$ that consists of successive GM-moves $x = x^0 \\to x^1 \\to \\ldots \\to x^j \\to \\ldots$ . If $range(x) = x_n - x_1 \\leq \\ell$ then for all $j \\geq 0$: (i) $range(x^j) \\leq \\ell$; (ii) the pivot of $x^{j + \\ell}$ is one less than the pivot of $x^j$, assuming that $1 - 1 = 0 = n$. (iii) $x_i^j - x_i^{j + n \\ell} = (n-1) \\ell$ for all $i = 1,\\ldots,n$. Due to (iii), we compute $x^j$ in time linear in $n, \\ell, \\log(j)$, and $\\sum^n_{i=1}\\log(|x_i|+1)$. For $\\ell = 2$ a slighty modified version of the GM-rule was recently introduced by Gurvich, Martynov, Maximchuk, and Vyalyi, \"On Remoteness Functions of Exact Slow $k$-NIM with $k+1$ Piles\", arXiv:2304.06498 (2023), where applications to impartial games were considered.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-11-06T16:41:26.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "impartial games",
      "applications",
      "rightmost minimal entry",
      "gm-rule respects monotonicity",
      "slighty modified version"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}