Cards with Numbers
An interesting Game Theory puzzle asked in an MIT lecture
Arthur and Bella play the following game with a deck of 25 cards. Every card has a distinct natural number on it from the set: S={1,2,…,25}.
Arthur first picks a card with even number x_0 and removes it from deck: We have S:=S−{x_0}.
Then they take turns (starting with Bella) picking a card with number x_n ∈ S which is either divisible by the previous number or divides it ( i.e. divisible by x_(n-1) or divides x_(n-1) ) and remove it from deck.
The player who can not find a number in deck which is a multiple or is divisible by the number on previous card loses.
Which player has the winning strategy ?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
Solution
Bella always has a winning strategy.
Divide the set S into {1} , { 13, 17, 19, 23 } and these pairs
{ (2,14) (3,15) (4,16) (5,25) (6,12)
(7,21) (8,24) (9,18)(10,20) (11,22) }
Arthur goes first and picks an even number card, Bella chooses the card with the other number from the pair containing that number. For eg, if Arthur chooses 2, Bella picks the 14 number card.
Bella will keep following the strategy for whatever number Arthur picks and keeps crossing the pairs. Note that Arthur can’t pick 13,17,19,23 unless the previous number drawn is 1. As the game goes on Arthur will be forced to pick 1 from the deck. The moment that happens Bella will pick one of {13,17,19,23} cards and win the game.
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!
Good one