Premium
A Nim‐like Game and Dynamic Recurrence Relations
Author(s) -
Gan BoonBeng,
Yeh YeongNan
Publication year - 1995
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1002/sapm1995952213
Subject(s) - combinatorics , mathematics , monotonic function , sequence (biology) , order (exchange) , integer (computer science) , function (biology) , degree (music) , duality (order theory) , discrete mathematics , physics , mathematical analysis , computer science , genetics , finance , evolutionary biology , acoustics , economics , biology , programming language
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.