From:           kubo@zariski.harvard.edu (Tal Kubo)
Newsgroups:     rec.puzzles,sci.math
Subject:        Generalized Fibonacci Nim
Date:           26 Mar 93 02:34:32 GMT
Organization:   Dept. of Math, Harvard Univ.

Consider the following game ("Generalized Fibonacci Nim") : 

  -- two players alternate in taking chips from a single heap
  -- the player to take the last chip wins
  -- at least one chip must be removed at each turn
  -- at each turn there is an upper limit L to the number of chips 
       which may be removed
  -- the upper limit varies as follows: given is a nondecreasing, 
       positive integer-valued function F, such that if a player removes  
       N  chips, then the upper limit for the next move is  F(N)

In Winning Ways, this game with  F(n)=2n  is referred to as 
Fibonacci Nim, because the winning strategy involves Fibonacci numbers.
In the general case, the winning strategy can be described in terms
of sequences satisfying a recurrence of the form  E(n)=E(n-1)+E(n-j),
where  j depends on   F and n  in a known way.  Deriving this winning
strategy, even for particular functions  F, is a very beautiful exercise.

I have some references to work done on this game in the 1970's by Schwenk,
Ferguson, and someone else whose name escapes me right now (it was part of
his doctoral dissertation at UCLA).   In their papers, the winning strategy
is derived.  What I would like to know is whether any work has been done
since then on characterizing the Nim-values (also called G-values, Grundy
numbers, or Sprague-Grundy numbers) for this class of games.  If you have
knowledge of such, please post or contact me at the e-mail address below.
Thanks.

Tal Kubo
kubo@math.harvard.edu

p.s.  Conjecturally, winning strategies and other invariants of 
generalized Nim games are connected with the classification of 
sequences satisfying Conway's recurrence   a(n)=a(a(n-1))+a(n-a(n-1)).

From:           jlame@math.ohio-state.edu (John Lame)
Newsgroups:     sci.math.research
Subject:        Take-Away Games
Date:           16 Jul 1996 14:29:30 -0400
Organization:   Department of Mathematics, The Ohio State University

Hi everyone,

Fibonacci Nim has the following rules.

A pile of N stones is placed between players 1 and 2 with N > 1. 
Player 1 goes first and may remove as many stones as desired
provided at least one stone is left in the pile. Players then take
turns removing 1 or more stones from the pile with the condition that:
If one player removes x stones, then the next player may remove at
most 2x stones.  The winner is the player who removes the last stone.

It turns out that player 2 has a guaranteed win if and only if
N is a Fibonacci number (2,3,5,8,...).

I was playing around with variations of this game and, in each
case, asking myself: For which initial pile sizes does player
2 have a guaranteed win?  In particular I'm interested in the
following variation, the only change being the addition of
condition (2).

A pile of N stones is placed between players 1 and 2 with N > 1. 
Player 1 goes first and may remove as many stones as desired
provided at least one stone is left in the pile. Players then take
turns removing 1 or more stones from the pile with two conditions.  
1) If one player removes x stones, then the next player may remove at
most 2x stones.  
2) Unless forced to, a player may not remove the same number of stones 
as they did on their last turn.

Note that the only instance in which a player may be forced to violate
rule (2) is in the case that there is a single stone remaining in the
pile.  The winner is the player who removes the last stone.

I have found that the following are all the initial pile sizes < 5000
which guarantee a win for player 2.

2 3 5 6 7 8 11 13 18 19 22 26 30 43 70 71 76 84 140 153 223 224 392 394
405 681 689 696 1149 1164 1747 1759 1760 2893 2894 2895 4773

I wrote a short program in C to generate various data related to this
game as well as play the game with the user. I'd be happy to mail it
to anyone interested. (although its poorly documented so be warned)

I'm posting this in the hopes that someone might be able to shed some
light on the nature of the above sequence.

There is a nice article on take-away games where the set of legal
moves on a given player's turn is a function of only the previous
move (as opposed to my variation in which the set of legal
moves on a given turn is a function of the previous two moves).
Those interested should read "Take-Away Games" by Allen J. Schwenk,
Fibonacci Quarterly 8 (1970) 225-234.

Thanks in advance,
John