February 2008
Ponder This Solution:
The game is played on a set of n pebbles using a parameter p.
Each player in turn takes some of the pebbles. Players must take at least one, but no more than p times the amount of pebbles the previous player took.
In the first move, where no pebbles were previously taken, the first player can take any number of pebbles up to n-1. If a player cannot take a turn, he or she loses.
The first player usually wins. The table lists, for a parameter p, the numbers for which the second player wins.
For example, when p=1, meaning that each player can take no more than the amount taken in the previous step, the winning strategy for the first player, if n is not a power of 2, is to take the highest possible power of 2 which divides n. One can see that if n is a power of 2, then the second player can win by taking the highest power of 2 which divides the first player’s move.
Similarly, p=2 gives the Fibonacci sequence as winning numbers for the second player (why?); and p=3 even appears in the On-Line Encyclopedia of Integer Sequences (http://www.research.att.com/~njas/sequences/A003411).
The missing values are
| Parameter | Sequence | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 1 | 2 | 3 | 4 | 6 | 8 | 11 | 15 | 21 | 29 | 40 | 55 | 76 | 105 | 145 | ... |
| 4 | 1 | 2 | 3 | 4 | 5 | 7 | 9 | 12 | 15 | 19 | 24 | 31 | 40 | 52 | 67 | ... |
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com