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*
5W2
6W*
7W4
8L (can only reach 2, 4, 6, or 7 but not 3)
9W1
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 20160204 20:20:26 