From: firstname.lastname@example.org (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 email@example.com 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: firstname.lastname@example.org (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