Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Sep 23, 2010

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!

5 comments:

  1. 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. 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. @sid.. correct solution! Bingo!

    @Tiger.. see sid's comment :)

    ReplyDelete
  4. 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. @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