About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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