1994 AIME Problems/Problem 9

From AoPSWiki

Problem

A solitarire game is played as follows. Six distinct pairs of matched tiles are placed in a bag. The player randomly draws tiles one at a time from the bag and retains them, except that matching tiles are put aside as soon as they appear in the player's hand. The game ends if the player ever holds three tiles, no two of which match; otherwise the drawing continues until the bag is empty. The probability that the bag will be emptied is $p/q,\,$ where $p\,$ and $q\,$ are relatively prime positive integers. Find $p+q.\,$

Solution

Let $P_k$ be the probability of emptying the bag when it has $k$ pairs in it. Let's consider the possible draws for the first three cards:

Case 1. We draw a pair on the first two cards. The second card is the same as the first with probability $\frac {1}{2k - 1}$ , then we have $k - 1$ pairs left. So this contributes probability $\frac {P_{k - 1}}{2k - 1}$ .
Case 2. We draw a pair on the first and third cards. The second card is different from the first with probability $\frac {2k - 2}{2k - 1}$ and the third is the same as the first with probability $\frac {1}{2k - 2}$ . We are left with $k - 1$ pairs but one card already drawn. However, having drawn one card doesn't affect the game, so this also contributes probability $\frac {P_{k - 1}}{2k - 1}$ .
Case 3. We draw a pair on the second and third cards. This is pretty much the same as case 2, so we get $\frac {P_{k - 1}}{2k - 1}$ .

Therefore, we obtain the recursion $P_k = \frac {3}{2k - 1}P_{k - 1}$ . Iterating this for $k = 6,5,4,3,2$ (obviously $P_1 = 1$ ), we get $\frac {3^5}{11*9*7*5*3} = \frac {9}{385}$ , and $p+q=\boxed{394}$ .

1994 AIME (Problems • Resources)
Preceded by Problem 8	Followed by Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox

1994 AIME Problems/Problem 9

From AoPSWiki

Problem

Solution

See also