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. 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

Post a Comment