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.
Every value of n is a forced win for either player A or Player B. Let S be the set of all n such that player B can force a win. Then Player's A strategy is to remove stones from the heap so that the remaining number of stones is in S.
Assume S is finite. Then S has a maximum. Call it M. And the number of elements of S must be less than M.
Consider all numbers between M+1 and 10^(2M). Clearly, these are all bigger than M, so none of them are in S. According to our assumption, A can convert each of these numbers to a number in S by subtracting one less then some prime number. The problem, there just aren't enough prime numbers to do this. By the prime number theorem, the number of primes between M and and 10^2M is less than 10^2M/log(10^2M) = 10^2M/2M. Because there are at most M numbers in S (and in fact are quite a few less), the most numbers that can possibly be transformed into an element of S is M*(10^2M/2M) = 10^2M/2, and that is just a fraction of the numbers between M+1 and 10^2M. So we have a contradiction, and the assumption is false.
Therefore, both players have an infinite number of n which they can use to force a win.
Edited on February 5, 2016, 10:02 am
Who needs a strategy? (spoiler)
