For any positive integer parameters a and b, Gurvich recently introduced a generalization mex<Subscript> b </Subscript> of the standard minimum excludant mex=mex<Subscript>1</Subscript>, along with a game NIM(a, b) that extends further Fraenkel’s NIM=NIM(a, 1), which in its turn is a generalization of the classical Wythoff NIM=NIM(1, 1). It was shown that P-positions (the kernel) of NIM(a, b) are given by the following recursion: <Equation ID="Equa"> <EquationSource Format="TEX">$$x_n={\rm mex}_b(\{x_i, y_i \;|\; 0 \leq i > n\}), \;\; y_n=x_n + an; \;\; n \geq 0,$$</EquationSource> </Equation>and conjectured that for all a, b the limits ℓ(a, b)=x <Subscript> n </Subscript>(a, b)/n exist and are irrational algebraic numbers. In this paper we prove that showing that <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\ell(a,b)=\frac{a}{r-1}}$$</EquationSource> </InlineEquation>, where r > 1 is the Perron root of the polynomial<Equation ID="Equb"> <EquationSource Format="TEX">$$P(z)=z^{b+1} - z - 1 - \sum_{i=1}^{a-1} z^{\lceil ib/a \rceil},$$</EquationSource> </Equation>whenever a and b are coprime; furthermore, it is known that ℓ(ka, kb)=kℓ(a, b). In particular, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$${\ell(a, 1)=\alpha_a=\frac{1}{2} (2 - a + \sqrt{a^2 + 4})}$$</EquationSource> </InlineEquation>. In 1982, Fraenkel introduced the game NIM(a) = NIM(a, 1), obtained the above recursion and solved it explicitly getting <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$${x_n=\lfloor \alpha_a n \rfloor, \; y_n=x_n + an=\lfloor (\alpha_a + a) n \rfloor}$$</EquationSource> </InlineEquation>. Here we provide a polynomial time algorithm based on the Perron–Frobenius theory solving game NIM(a, b), although we have no explicit formula for its kernel. Copyright Springer-Verlag 2013
