Summer Problem Solving Marathon Solution #9

Let P_n be the probability of winning the game when it is played with n pairs of cards in the deck. Clearly P₁ = P₂ = 1, because the game cannot be lost with either 1 or 2 pairs in the deck.

Suppose we already know the value of P_n-1, and we are thinking about what happens in the game with n pairs. Here are four possibilities:

#1: The first two cards we draw form a pair. This pair is then discarded, and from this point on, the game proceeds as if it were a game with n-1 pairs, so the probability of victory from this point is P_n-1.

#2: The first two cards are different, but the third card matches the first. Then the pair formed by the first and third cards is discarded, and play continues as if it were a game with n-1 pairs (with the first card already drawn, but this does not affect the probabilities). So the probability of victory from this point is P_n-1.

#3: The first two cards are different, but the third card matches the second. Then the pair formed by the second and third cards is discarded, and play continues as if it were a game with n-1 pairs. Again, the probability of victory from this point is P_n-1.

#4: The first three cards are all different. The player then loses.

These four options are exclusive and exhaustive, so the sum of their probabilities of occurring must be 1. Consider the probability of the fourth option. Once the first card is drawn, 2n-1 cards remain. 2n-2 of these are different from the first card, so there is a ^2n-2⁄_2n-1 chance that the first two cards will be different.

After the second card has been drawn, 2n-2 cards remain. Of these, 2n-4 are different from both the first and the second card. So the probability that the third card will not match the first or the second is ^2n-4⁄_2n-2.

So the chance that the first three cards are all different is ^2n-2⁄_2n-1 x ^2n-4⁄_2n-2 = ^2n-4⁄_2n-1.

So the chance that one of the first three options occurs is 1 - ^2n-4⁄_2n-1 = ^{2n-1 - (2n-4)}⁄_2n-1 = ³⁄_2n-1.

Given that one of the first three options occurs, the probability of victory is P_n-1>. So P_n, the overall probability of victory when there are n pairs, is ^3P_n-1⁄_2n-1.

We already know that P₂ = 1. So using this formula, we have:

P₃ = ^3x1⁄₅ = ³⁄₅.
P₄ = ^{3 x 3⁄₅}⁄₇ = ⁹⁄₃₅.
P₅ = ^{3 x 9⁄₃₅}⁄₉ = ³⁄₃₅.
P₆ = ^{3 x 3⁄₃₅}⁄₁₁ = ⁹⁄₃₈₅.

So the probability of victory is ⁹⁄₃₈₅.