A Nim‐like Game and Dynamic Recurrence Relations
Boon‐Beng Gan, Yeong‐Nan Yeh · Studies in Applied Mathematics · 1995
The nim‐like game 〈n, f; X, Y〉 is defined by an integern≥ 2 a constraint functionf, and two players andXandY. PlayersXandYalternate taking coins from a pile ofncoins, withXtaking the first turn. The winner is the one who takes the last coin. On thekth turn, a player may removetkcoins, where 1 ≤t1≤n− 1 and 1 ≤tk≤ max{1,f(tk−1) fork> 1. Let the setSf= {1} ∪ {n| there is a winning strategy forYin the nim‐like game 〈n,f;X,Y〉}. In this paper, an algorithm is provided to construct the setSf= {a1,a2,…} in an increasing sequence when the functionf(x) is monotonic. We show that if the functionf(x) is linear, then there exist integersn0andmsuch thatan+1=an+an−mforn>n0and we give upper and lower bounds form(dependent onf. A duality is established between the asymptotic order of the sequence of elements inSfand the degree of the functionf(x). A necessary and sufficient condition for the sequence {a0,a1,a2,…} of elements inSfto satisfy a regular recurrence relation is described as well.