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?



Solution:

Highlight the part between the * symbols for the answer.
* B (the second mover) wins, by a pairing strategy.

Pair up twenty of the numbers as:
(2,14) (3,15) (4,16) (5,25) (6,12) (7,21) (8,24) (9,18) (10,20) (11,22)
- each pair is a (divisor, multiple) couple, and every even number in 1..25 is in a pair. The leftovers are 1, 13, 17, 19, 23.

Strategy: after A's opening even x_0, B plays x_0's partner (legal - partners divide each other). Thereafter, whenever A plays a paired number, B instantly plays its partner. The pairs are removed whole, so A always faces intact pairs plus leftovers. A's only other options:
- play 1: B answers 23. A must then play a multiple or divisor of 23 - but 46 > 25 and 1 is gone - A has no move and loses.
- play 13, 17 or 19 (each compatible only with 1): B answers 1. A may then play anything, B resumes pairing; but now 13, 17, 19, 23 are all dead (their only partner 1 is gone), so the game is consumed pair by pair with B always having the reply.

Since B always has a legal response and the pile is finite, A is the first player stuck without a move. B wins.

Solution by Mike Earnest from the comments (verified by exhaustive game-tree simulation: B wins against all A strategies). *

Comments

  1. Mike Earnest11:48 PM, August 02, 2013

    This comment has been removed by the author.

    ReplyDelete
  2. Mike Earnest1:52 AM, August 06, 2013

    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. Unknown3:06 AM, August 20, 2013

    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. Ajeet Kumar8:56 PM, August 20, 2013

      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. chera4:34 PM, August 23, 2013

      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. dumb phoenix1:17 PM, October 15, 2013

    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. Unknown12:52 PM, October 05, 2015

      I think that u have to start with a even number

      Delete
  5. Pratik Poddar1:48 AM, September 14, 2026

    Correct - the pairing strategy is airtight: each pair has the divisibility link internally, so B always has a legal response; the leftover pool {1,

    ReplyDelete
  6. Pratik Poddar1:49 AM, September 14, 2026

    Does not survive Mike's pairing: A opens 16, B responds 4 (its pair), and from then on B always has the paired response. A is the one who gets pushe

    ReplyDelete
  7. Pratik Poddar1:49 AM, September 14, 2026

    Good observation - the pairing only needs each pair to be internally linked and the leftover pool to be poisoned for A, and your alternatives show t

    ReplyDelete
  8. Pratik Poddar1:50 AM, September 14, 2026

    Checks out - after A removes 18, every remaining number except {1, 17, 19, 23} sits in a linked pair, so A mirrors B's moves inside pairs; B is firs

    ReplyDelete
  9. Pratik Poddar1:51 AM, September 14, 2026

    B does not start - A opens by removing an even number, THEN B moves. 23 is never available as an opening. With correct move order, B still wins (Mike

    ReplyDelete
  10. Pratik Poddar5:43 AM, September 14, 2026

    Exactly - A's first pick must be even; that constraint is built into the pairing-strategy analysis abov

    ReplyDelete

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

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