A Nim‐like Game and Dynamic Recurrence Relations

The nim‐like game 〈n, f; X, Y〉 is defined by an integer n ≥ 2 a constraint function f , and two players and X and Y . Players X and Y alternate taking coins from a pile of n coins, with X taking the first turn. The winner is the one who takes the last coin. On the k th turn, a player may remove t k coins, where 1 ≤ t 1 ≤ n − 1 and 1 ≤ t k ≤ max{1, f ( t k −1 ) for k > 1. Let the set S f = {1} ∪ { n | there is a winning strategy for Y in the nim‐like game 〈 n , f ; X , Y 〉}. In this paper, an algorithm is provided to construct the set S f = { a 1 , a 2 ,…} in an increasing sequence when the function f ( x ) is monotonic. We show that if the function f ( x ) is linear, then there exist integers n 0 and m such that a n+1 = a n + a n−m for n > n 0 and we give upper and lower bounds for m (dependent on f . A duality is established between the asymptotic order of the sequence of elements in S f and the degree of the function f ( x ). A necessary and sufficient condition for the sequence { a 0 , a 1 , a 2 ,…} of elements in S f to satisfy a regular recurrence relation is described as well.