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

Aug 2, 2013

Combinatorics + Game Theory Puzzle


Source: Random search on http://math.stackexchange.com/

Problem:

Two players A and B play the following game:

Start with the set S of the first 25 natural numbers: S={1,2,…,25}.

Player A first picks an even number x_0 and removes it from S: We have S:=S−{x_0}.

Then they take turns (starting with B) picking a number x_n∈S which is either divisible by x_n-1 or divides x_n-1 and removing it from S.

The player who can not find a number in S which is a multiple or is divisible by the previous number looses.

Which player has the winning strategy and what is it?

7 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. B wins. Pair up the numbers in 1...25, except for 1 and primes more than 11, as below:

    (2,14) (3,15)
    (4,16) (5,25)
    (6,12) (7,21)
    (8,24) (9,18)
    (10,20) (11,22)

    When A chooses one of the above numbers, B responds with the other in its pair, which will ensure B always has a number to choose. A will eventually have to pick 1, to which B responds with 23 for the win.

    ReplyDelete
  3. A wins. He chooses 16 on his first chance, and on his next he chooses a multiple of 3. After a few moves, B will be forced to choose 1, when A chooses 23

    ReplyDelete
    Replies
    1. Certainly B wins as pointed out by Mike Earnest, but the pairs of number as response for B is not unique.
      Certain pairs are uniquely determined. They are:
      (22,11); (18,9); (2,14); (10,20); (5,25); (3,15); (21,7)

      They have also been pointed out by Mike. But for other the following three sets of possibility are there:

      1st : (4,16); (8,24); (6,12) % Same as that pointed by mike
      2nd : (8,16); (4,24); (6,12)
      3rd : (8,16); (4,12); (6,24)

      so say if A chooses 24, then B can respond with 8, 6 or 4.

      The substantive question is if n is any natural number, is there always a wining strategy for B?

      Delete
    2. if n=27, then A has a winning strategy,

      A will choose 18. then the remaining numbers are paired thus:

      (2,14) (3,15)
      (4,16) (5,25)
      (6,12) (7,21)
      (8,24) (9,27)
      (10,20)(11,22)
      (13,26)

      unpaired nos. are {1,17,19,23}

      A will follow the strategy of completing pair. ultimately B will choose 1, then A will choose 23.

      Delete
  4. Note that B starts. I claim that B wins.
    B chooses 23, A has to choose 1
    B chooses 17, A has nothing to choose!

    ReplyDelete
    Replies
    1. I think that u have to start with a even number

      Delete