# Fibonacci Nim

## Fibonacci Numbers

1,1,2,3,5,8,13,21,34,55,89: what's next?

If you guessed 144, you may be on to something we call the Fibonacci numbers, after a mathematician who lived about 1200 A.D..

The Fibonacci numbers are generally defined this way: given the two latest Fibonacci numbers, create the next (and newest) Fibonacci by adding them together. So 1+1=2, 1+2=3, 2+3=5, etc. We explain this all mathematically via the **recursive algorithm** that follows:

```
F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2),
```

These numbers appear all over in nature: in pinecones, pineapples, artichokes, pussywillows, daisys, etc.

But they started out as pairs of immortal bunnies, which mature in a month, and then produce a single new pair every month thereafter (that's the way Fibonacci began studying them, it seems). We start out on the left, in the diagram which follows, and watch a single baby bunny pair mature, and then begin to populate the world with bunny pairs:

This diagram illustrates why the recursive algorithm works:

- we assume that the number of bunny pairs arising from a single immature pair is given by the sequence , with generations 1, 2, 3, 4, 5 shown here (although this will continue on forever, of course).
- We notice that at the third generation, the total population of pairs is given by the sum of two new populations: a perfect copy of the original tree, starting from the first generation, and a perfect copy of the original tree starting from the second generation.
- Hence , , and so on. So, more generally,

## Fibonacci number decomposition

We "decompose" natural numbers using Fibonacci numbers and sums:

every natural number is either

- Fibonacci, or
- can be written as a sum of
**non-consecutive**Fibonacci's in a unique way.

Examples?

Can we justify this?

- If a number is Fibonacci, then we're done.
- Assume a number is not Fibonacci:
- then there is a largest Fibonacci that "fits inside it" -- e.g. 24 = 21 + 3.
- If the remainder (3, in the example above), after subtraction, is Fibonacci, how do we know that it is not consecutive (that is, that it is not 13)? That is, how do we know that the two Fibonacci numbers are not successive Fibonacci numbers?

Because if they were, they could be combined to form a larger Fibonacci number! And we chose the largest Fibonacci possible to start. - If it is not Fibonacci, can we not simply repeat the current process of looking for a sum for a non-Fibonacci number, but using the remainder instead of the original number? (i.e. can we not simply "recurse" -- that is, do it again, and so construct a chain of numbers leading down towards 1.
**Example**: 33=21+12=21+8+4=21+8+3+1

## Fibonacci Nim

- Rules:
- Two players,
*n*sticks (coins/bottlecaps/etc) - First player must take anywhere from 1 to
*(n-1)*sticks - From then on, the next player may take from 1 up to twice what the previous player took.
- Winner is the player who picks up the last stick

- Two players,
- Is there a winning strategy?
- Is there a perfect defensive strategy?
- Let's look at the early examples: If you looked at some special cases, what can we conclude?
Number of sticks *n*1 2 3 4 5 6 7 8 Winner X P2 P2 P1 P2 P1 P1 P2