IBM Research | Ponder This | February 2008 solutions

# Ponder This

## February 2008

<<January February March>>

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
312346811152129405576105145...
412345791215192431405267...

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com