Fibonacci NIM

Set up: Put out some tokens. For a game that is always winable by the first player, put out a non-Fibonacci number of tokens.

Rules:

On the first turn, the player must take at least 1 token, and can't take all of the tokens

On every turn after the first turn of the game, the player must take at least 1 token, and at most twice as many as the person who went before him/her.

The person who takes the last token wins.

Sample game 1 (as played by clueless people):

Start with 12 tokens:

The first player can take 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, or 11 tokens.

The first player takes 5 tokens:

The second player can take 1, 2, 3, 4, 5, 6, 7, 8, 9, or 10 tokens. The second player takes all of the remaining tokens, and wins

Sample game 2 (as played by only slightly less clueless people).

Start with 12 tokens:

The first player can take 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, or 11 tokens.

The first player takes 2 tokens:

The second player can take 1, 2, 3, or 4. The second player takes 2 tokens

The first player can now 1, 2, 3, or 4. The first player takes 1 token

The second player can take 1 or 2 tokens. The second player takes 2 tokens

The first player can take 1 or 2 tokens. The first player takes 1 token

The second player can take 1 or 2 tokens. The second player takes 1 token

The first player realizes that no matter whether he/she takes 1 or 2 tokens, player 2 will still win at the next round, and concedes the game.

Sample game 3: How to Win. (Fred Fibonacci vs. Sam Sleepy)

Start with 12 tokens:

Fred Fibonacci: The best Fibonacci sum for 12 is 12=8+3+1. Take 1 token.

Sam Sleepy (doomed no matter what he does): 11 tokens left. 11=8+3, but Sam can only take 1 or 2 tokens. Sam takes 1:

Fred Fibonacci: 10 tokens left. The best Fibonacci sum for 10 is 10=8+2. Take 2 tokens.

Sam Sleepy: 8 tokens left (which is a Fibonacci number). Sadly, Sam is not allowed to take 8. Sam can only take 1 or 2 tokens. Sam takes 2:

Fred Fibonacci: 6 tokens left. The best Fibonacci sum for 6 is 6=5+1. Take 1 tokens.

Sam Sleepy: 5 tokens left (which is a Fibonacci number). Sadly, Sam is not allowed to take 5. Sam can only take 1 or 2 tokens. Sam takes 2:

Fred Fibonacci: 3 tokens left. 3 is a Fibonacci number. normally, that would be bad, but--WooHoo! Sam took 2 last time, so Fred is allowed to take all 3! He does, and wins!

Sample game 4: showing winning moves for Fred