Fibonacci nim is a mathematical

subtraction game In combinatorial game theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers (for instance, the numbers of game tokens in piles of tokens, or the positions of pieces on board) ...

, a variant of the game of

nim Nim is a mathematical two player game. Nim or NIM may also refer to: * Nim (programming language) * Nim Chimpsky, a signing chimpanzee Acronyms * Network Installation Manager, an IBM framework * Nuclear Instrumentation Module * Negative index met ...

. Players alternate removing coins from a pile, on each move taking at most twice as many coins as the previous move, and winning by taking the last coin. The

Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...

s feature heavily in its analysis; in particular, the first player can win if and only if the starting number of coins is not a Fibonacci number. A complete strategy is known for best play in games with a single pile of counters, but not for variants of the game with multiple piles.

Rules and history

Fibonacci nim is played by two players, who alternate removing coins or other counters from a pile. On the first move, a player is not allowed to take all of the coins, and on each subsequent move, the number of coins removed can be any number that is at most twice the previous move. According to the

normal play convention A normal play convention in a game is the method of determining the winner that is generally regarded as standard. For example: *Preventing the other player from being able to move *Being the first player to achieve a target *Holding the highest va ...

, the player who takes the last coin wins. The game was first described by Michael J. Whinihan in 1963, crediting its invention to

Oregon State University Oregon State University (OSU) is a public land-grant, research university in Corvallis, Oregon. OSU offers more than 200 undergraduate-degree programs along with a variety of graduate and doctoral degrees. It has the 10th largest engineering co ...

mathematician Robert E. Gaskell. It is called Fibonacci nim because the

s feature heavily in its analysis. This game should be distinguished from a different game, also called Fibonacci nim, in which players may remove any Fibonacci number of coins on each move.

Strategy

The strategy for best play in Fibonacci nim involves thinking of the current number of coins as a sum of

s. There are many ways of representing numbers as sums of Fibonacci numbers, but only one representation that uses each Fibonacci number at most once, and avoids consecutive pairs of Fibonacci numbers; this unique representation is known as its Zeckendorf representation. For instance, the Zeckendorf representation of 10 is 8 + 2; although 10 can also be represented as sums of Fibonacci numbers in other ways, such as 5 + 5 or 5 + 3 + 2, those other ways do not meet the condition of only using each Fibonacci number once and avoiding consecutive pairs of Fibonacci numbers such as the pairs 2, 3 and 3, 5. The Zeckendorf representation of any number may be found by a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

that repeatedly subtracts the largest Fibonacci number possible, until reaching zero. The game strategy also involves a number called the "quota", which may be denoted as . This is the maximum number of coins that can currently be removed. On the first move, all but one coin can be removed, so if the number of coins is then the quota is . On subsequent moves, the quota is two times the previous move. Based on these definitions, the player who is about to move can win whenever is greater than or equal to the smallest Fibonacci number in the Zeckendorf representation, and will lose (with best play from the opponent) otherwise. In a winning position, it is always a winning move to remove all the coins (if this is allowed) or otherwise to remove a number of coins equal to the smallest Fibonacci number in the Zeckendorf representation. When this is possible, the opposing player will necessarily be faced with a losing position, because the new quota will be smaller than the smallest Fibonacci number in the Zeckendorf representation of the remaining number of coins. Other winning moves may also be possible. However, from a losing position, all moves will lead to winning positions. The Zeckendorf representation of a Fibonacci number consists of that one number. So when the starting pile has a Fibonacci number of coins, the smallest Fibonacci number in the Zeckendorf representation is just , larger than the starting quota . Therefore, a Fibonacci number as the starting pile is losing for the first player and winning for the second player. However, any non-Fibonacci starting number of coins has smaller Fibonacci numbers in its Zeckendorf representation. These numbers are not larger than the starting quota, so whenever the starting number of coins is not a Fibonacci number, the first player can always win.

Example

For example, suppose that there are initially 10 coins.The fact that 2 is the unique winning move from this starting position, and the Zeckendorf representations of all pile sizes arising in this example, can be seen in , Table 1, p. 818. *The Zeckendorf representation of 10 is 10 = 8 + 2, and the initial quota is 9, larger than the smallest Fibonacci number 2 in the Zeckendorf representation, so the first player can win. One winning move by the first player would be to remove the smallest Fibonacci number in this representation, 2, leaving 8 coins. *After this move, there are 8 coins left, with Zeckendorf representation 8, and the new quota is 4, meaning that the second player can remove at most 4 coins, not enough to reach the smallest number in the Zeckendorf representation. Removing 3 or 4 coins would allow the first player to win immediately; suppose instead that the second player takes 2 coins. *This leaves 6 = 5 + 1 coins, with a quota of 4, larger than the 1 in the Zeckendorf representation. The first player can again takes the smallest Fibonacci number in this representation, 1, leaving 5 coins. *With a pile of 5 coins, the Zeckendorf representation is 5, but the quota is 2, a smaller number. The second player could take two coins, but that would again lose immediately, so suppose that the second player takes only one coin. *After this move, the number of coins is 4 = 3 + 1, and the quota is 2. The first player again takes the smallest Fibonacci number in the Zeckendorf representation, 1, leaving 3 coins. *Now, regardless of whether the second player takes one or two coins, the first player will win the game in the next move.

Multiple piles

Fibonacci nim is an

impartial game In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference betw ...

in that the moves that are available from any position do not depend on the identity of the player who is about to move. Therefore, the

Sprague–Grundy theorem In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...

can be used to analyze an extension of the game in which there are multiple piles of coins, and each move removes coins from only one pile (at most twice as many as the previous move from the same pile). For this extension, it is necessary to compute the nim-value of each pile; the value of the multi-pile game is the

nim-sum In mathematics, the nimbers, also called ''Grundy numbers'', are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with ''nimber addition'' and ' ...

of these nim-values. However, a complete description of these values is not known. A different multiple-pile variant of the game that has also been studied limits the number of stones in each move to twice the number from the previous move, regardless of whether that previous move was to the same pile.

References

{{reflist, refs= {{citation, last1=Allen, first1=Cody, last2=Ponomarenko, first2=Vadim, doi=10.2140/involve.2014.7.807, issue=6, journal=Involve, title=Fibonacci Nim and a full characterization of winning moves, volume=7, year=2014, pages=807–822 , doi-access=free {{citation, first1=Ronald L., last1=Graham, author1-link=Ronald Graham, first2=Donald E., last2=Knuth, author2-link=Donald Knuth, first3=Oren, last3=Patashnik, author3-link=Oren Patashnik, title=Concrete Mathematics, title-link=Concrete Mathematics, edition=2nd, year=1994, publisher=Addison-Wesley, pages=295–296, isbn=0-201-55802-5 {{citation , last1 = Larsson , first1 = Urban , last2 = Rubinstein-Salzedo , first2 = Simon , arxiv = 1410.0332 , doi = 10.1007/s00182-015-0473-y , issue = 3 , journal = International Journal of Game Theory , mr = 3538534 , pages = 617–625 , title = Grundy values of Fibonacci nim , volume = 45 , year = 2016, s2cid = 206890376 {{citation, last1=Larsson, first1=Urban, last2=Rubinstein-Salzedo, first2=Simon, doi=10.1007/s00182-017-0574-x, issue=2, journal=International Journal of Game Theory, mr=3842045, pages=595–611, title=Global Fibonacci nim, volume=47, year=2018, s2cid=52073784 For the game of subtracting Fibonacci numbers of coins, see {{citation, first=Brother U., last=Alfred, title=Exploring Fibonacci numbers, url=http://www.fq.math.ca/Scanned/1-1/alfred3.pdf, journal=

Fibonacci Quarterly The ''Fibonacci Quarterly'' is a scientific journal on mathematical topics related to the Fibonacci numbers, published four times per year. It is the primary publication of The Fibonacci Association, which has published it since 1963. Its founding ...

, volume=1, issue=1, pages=57–63, year=1963, "Research project: Fibonacci nim", p. 63; {{citation, first1=Jeremy C., last1=Pond, first2=Donald F., last2=Howells, title=More on Fibonacci nim, url=http://www.fq.math.ca/Scanned/3-1/pond.pdf, journal=

, volume=1, issue=3, pages=61–62, year=1963 {{citation, title=Mathematical Games and How to Play Them, series=Dover Books on Mathematics, first=Steven, last=Vajda, publisher=Courier Corporation, year=2007, isbn=9780486462776, contribution-url=https://books.google.com/books?id=F4epmWVyqW8C&pg=PA28, contribution=Fibonacci nim, pages=28–29 {{citation, first=Michael J., last=Whinihan, title=Fibonacci Nim, url=http://www.fq.math.ca/Scanned/1-4/whinihan.pdf, journal=

, volume=1, issue=4, pages=9–13, year=1963 Combinatorial game theory Fibonacci numbers Mathematical games