Fibonacci Nim

DIRECTIONS
Play a game of Fibonacci Nim and beat Nim. Here's how...

The object of the game is to take the last coin remaining. If you want to play with more or less Smiley coins than 100, click the New Game button. Enter the number of coins you like, and press the ENTER key. The minimum number of coins is 2 and the maximum number of coins is 1600. Next enter how many coins you want to take off the board. The minimum number is 1 and the maximum on the first play is one less than the initial number of coins. If you start with 100 coins, you can only take 99 coins maximum on the first move. But you don't want to take the maximum, or you will lose. Why? Because after you remove coins, Nim may take up to twice as many as you took, and then he will win. After Nim plays, you may take from 1 to twice as many as Nim took. Play continues until You or Nim takes the last coin. Play a game and see how it works.

STRATEGY
Here is how to always win using Fibonacci numbers: On the first move, leave Nim a Fibonacci number of coins, or Nim will leave you with a Fibonacci number of coins and force you to lose. If possible without losing, always leave Nim a Fibonacci number of coins. But don't take too many, or Nim will take the rest. Otherwise, count the number of coins remaining. (If the count is a Fibonacci number, Nim will win no matter what you do.) Write down the number of coins on the board as the SUM of nonconsecutive Fibonacci numbers. Find the smallest Fibonacci number in the sum. Remove that number of coins from the board. Repeat this process each time you play.

For example, if 15 coins remain on the board, write 15 as the sum of 13 + 2. Then remove 2 coins leaving 13. Nim can then only remove 1 to twice as many coins as you removed: that would be 1 to 4 coins. Suppose Nim removes 2 coins leaving 11. Write 11 as 8+3. Then remove 3 coins leaving 8. Nim can now remove 1 to 6 coins (2x3=6). Suppose Nim removes 2 coins leaving 6. Write 6 as 5+1. Then remove 1 coin leaving 5. Nim can only remove 1 or 2 coins now. Suppose Nim removes 1 coin leaving 4. Write 4 as 3+1. Then take 1 coin leaving 3. If Nim takes 1 coin, you will take 2 coins and win! If Nim takes 2 coins, you will take the last coin and win! Using this strategy, you will always win if you leave Nim a number of coins equal to the sum of Fibonacci numbers. Remember also that every Fibonacci number is the sum of Fibonacci numbers. So, if possible leave Nim a Fibonacci number of coins. Just make sure Nim cannot take all the remaining coins.

ASSIGNMENT

Play a game with 36 coins.
Win the game using the strategy described above.
Screencopy the results.
Email a gif image to your instructor.
Answer this question by playing a game with 34 coins:
If you start with a Fibonacci number of coins, is Nim smart enough to beat you?