All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 a version of NIM (Posted on 2016-02-04)
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.

Comments: ( Back to comment list | You must be logged in to post comments.)
 Who needs a strategy? (spoiler) | Comment 1 of 3
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
 Posted by Steve Herman on 2016-02-04 16:38:00

 Search: Search body:
Forums (0)