A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory (Q378342): Difference between revisions

Recently, Gurvich introduced an interesting generalization of Wythoff's game. Let \(a\), \(b\) be positive integers. In the subtraction game \(\mathrm{NIM}(a,b)\) played with two piles with respectively \(x\) and \(y\) token, it is allowed to remove \(x'\) and \(y'\) token from these two piles if and only if \(0\leq x'\leq x\), \(0\leq y'\leq y\), \(0<x'+y'\) and either \(|x'-y'|<a\) or \(\min(x',y')<b\). For the normal version of the game, a recursive characterization of the set of \(P\)-positions \(\{(x_n,y_n)\mid n\geq 0\}\) based on a generalization of the minimum excludant (mex) operator is known. Contrarily to the usual setting, note that \(\mathbb{Z}_{\geq 1}\setminus \{x_n,y_n\mid n\geq 0\}\) is infinite. In this paper, the authors consider the limit \(\ell(a,b)=\lim_{n\to\infty}x_n/n\). They prove that it exists and is equal to \(a/(r-1)\), where \(r>1\) is the Perron root of the polynomial \[ z^{b+1}-z-1-\sum_{i=1}^{a-1}z^{\lceil ib/a\rceil} \] whenever \(a,b\) are coprime. This polynomial is the characteristic polynomial of a non-negative square matrix depending only on \(a\) and \(b\). Moreover, if \(a=da'\) and \(b=db'\), then \(\ell(a,b)=d\, \ell(a',b')\). The values \(x_n\) and \(y_n\) can be computed in \(O(g(a,b)\log n)\) iterations, where \(g(a,b)\) is a constant. Even if closed formulas for \(x_n\) and \(y_n\) are not known, a polynomial algorithm to play \(\mathrm{NIM}(a,b)\) is derived. In the last section, the misère version is also considered (this leads only to minor modifications).