Alice and Bob play a game in which they take turns removing stones from a heap that initially has n stones.
The number of stones removed at each turn must be one less than a prime number. Alice goes first.

The winner is the player who takes the last stone.

Prove that there are infinitely many values of n such that Bob has a winning strategy.

I had a bit of trouble following Steve's proof so I tried to see how the game behaves fro various n.

Each starting position is either a Win for A or a Lose for A (win for B).
W* means a win in one move (one less than a prime) W with a number indicates how many A should take to reach an L.
0L (if you see 0 on your turn you just lost)
1W*
2W*
3L (can only reach 1 or 2)
4W*
5W-2
6W*
7W-4
8L (can only reach 2, 4, 6, or 7 but not 3)
9W-1
10W*
11L (can only reach 1,5,7,9,10 but not 3 or 8)
12W*
...and so on up to 31 every position is a W...
32L (can't reach 3, 8, or 11)

There aren't many L's.   At first glance it seems they may peter out. 
However, as Steve points out, there will eventually be a position that can't reach 3, 8, 11, or 32 because at some point there just aren't enough primes to choose from to hit one of these targets.

Surprisingly there doesn't seem to be an OEIS entry for the sequence 3,8,11,32

Posted by Jer on 2016-02-04 20:20:26