(The published version is available online.)

Fibonacci Nim is a variant of the game of Nim, in which two players alternately remove one or more stones from a single pile, with the player removing the last stone being the winner. On his initial move, the first player may remove any number of stones, so long as he leaves at least one. On each subsequent move, a player may remove at most twice as many stones as the previous player took. It turns out that the `losing positions', namely the sizes of the initial pile from which the first player has no winning strategy, are precisely the Fibonacci numbers.

Several authors have considered variants of this game, in which at each step a player may remove at most c times as many stones as his opponent has just removed, for some fixed c>1.  Schwenk showed that the sequence of losing positions  H₁ < H₂ < ...  satisfies a recursion H_i+1 = H_i+H_i-k  for all sufficiently large i, where k does not depend on i. In Winning Ways,  Berlekamp, Conway, and Guy asked what one could say about k. We prove upper and lower bounds on k, which together imply that k is asymptotic to c log c as c→∞.  We also prove similar results in case each player is allowed to remove at most a prescribed linear function of the number of stones removed by his opponent.

Additional comment added October 2008:  Some of our results were later rediscovered by Frankl and Tokushige.

Michael Zieve:  home page   publication list