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

Home > Games
a version of NIM (Posted on 2016-02-04) Difficulty: 3 of 5
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.

No Solution Yet Submitted by Ady TZIDON    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information