Two players start with a number of counters.

competition/games/fibonacci.nim New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Two players start with a number of counters.  They play alternately,
removing one or more counters.  The first player may take as many as he
likes but not the whole pile.  Thereafter any player may remove up to
twice as many counters as the other has just removed.  The object of
the game is to remove the last counter.

For what numbers of initial counters can the second player force a win?
What is the best strategy?

-- Larry Taylor, October 1997

Show solution

This is solved in Knuth, The Art of Computer Programming, Vol 1:
Fundamental Algorithms.  See the answer to Exercise 1.2.8-37.  I have
the second edition, and the answer is on page 493.

Knuth reports a winning strategy, and states that the first player can
always win unless the initial number of counters is a Fibonacci number.
If the first player cannot force a win, he must leave a position from
which the second player can force a win.  Thus the second player wants
to start with a Fibonacci number of counters.

-- Dave Dodson <dodson@rsn.hp.com>