Prime Number Strategy Game

Disclaimer: Difficult Problem

Source: Amol Sahasrabudhe (Associate, Morgan Stanley) - Got his permission to put it on blog \m/ \m/

Problem: Lets consider a two player game in which a number is given. The first person gets a chance to choose a number of the form (prime-1) and subtract it from the given number. Then the second person gets a chance to do the same and so on. The person who makes the number zero wins.

So, if the chosen number is of the form (prime-1), the first person would win in the first chance. There are infinite numbers for which first person has a winning strategy. Prove that second person also has a winning strategy for infinite numbers. :)

Bonus: Given a chance to choose whether you want to be first person or second person, what would you choose?

Update (25-09-10)
Solution: Posted by Siddhant Agarwal (4th year, EE, IITB) in comments!

Comments

  1. Tiger12:05 PM, September 23, 2010

    assuming the problem, the bonus is obvious. neither. since both have countably infinite starting points which have winning strategies, it doesn't matter if ur first or second.

    ReplyDelete
  2. sid11:20 AM, September 24, 2010

    Let P = {x|x=prime-1}
    Let A = {x|player 1 has a winning strategy for x}
    Let B = {x|player 2 has a winning strategy for x}
    By convention zero belongs to B

    (We note that A and B form a partition of natural numbers)

    It is clear that an element y belongs to A iff there exists an element z belonging to P s.t. (y-z) belongs to B.

    So let the elements of B be finite. Hence it has a maximum. Let that be n. Consider the number m=(n+2)!+n+1. Now clearly m does not belong to P. Also as m,m-1,..m-(n-1) are all composite, hence m - any element of P will be greater than n. Hence m belongs to B. Contradiction!

    let b(n) = no of elements belonging to B less equal n, n>0

    Now as 1,2 belong to P, this implies [b(n)/n] <=1/3 for all n.

    Hence the density of B is less than 1/3. So If u have an option become the first player

    ReplyDelete
  3. Pratik Poddar10:32 AM, September 25, 2010

    @sid.. correct solution! Bingo!

    @Tiger.. see sid's comment :)

    ReplyDelete
  4. sid10:29 AM, December 09, 2010

    Just realized that this is the A2 problem of the 67th putnam competition of 2006..
    Here is the link
    http://mysite.science.uottawa.ca/dmdsg/McDonald/Putnam/exam2006.pdf

    ReplyDelete
  5. Gautam3:36 PM, December 13, 2010

    @Sid :
    Will m=(Product of all elements of B)-1 also give a contradictory situation?
    This seems like the problem of proving that there exists an infinitude of primes.

    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more