A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory

摘要

For any positive integer parameters a and b, Gurvich recently introduced a generalization mexj, of the standard minimum excludant mex = mex_1, along with a game NIM(a,6) 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: x_n = mex_b({x_i, y_i | O≤ i < n}), y_n = x_n + an; n ≥ 0, and conjectured that for all a, b the limits l(a, b) = x_n(a, b) exist and are irrational algebraic numbers. In this paper we prove that showing that l(a, b) = a/(r-1), where r > 1 is the Perron root of the polynomial, P(z)=z~(b+1)-z-1-∑_(i=1)~(a-1) z~([ib/a]), whenever a and b are coprime; furthermore, it is known that l(ka, kb) = kl(a, b). In particular, l(a, 1) = α_a = 1/2(2 - a + (a~2+4)~(1/2)). In 1982, Fraenkel introduced the game NTM(a)=NTM(a, 1), obtained the above recursion and solved it explicitly getting x_n = [α_an], y_n = x_n + an = |_(α_a + a)n]. 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.