1994 AIME Problem 9

Question

A solitaire 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

\frac{p}{q},

where

p

and

q

are relatively prime positive integers. Find

p+q.

Answer

Answer: 394

Concepts:recursive probability sampling without replacement process simulation

Difficulty rating: 2460

Small hint:

Track the number

r

of unseen pairs and the number

h

of unmatched tiles currently held

Big hint:

From state

(r,h)

, the next tile either matches one of the

h

held tiles or opens one of the

r

unseen pairs

Solution:

Let

F(r,h)

be the chance of success with

r

unseen pairs and

h\leq2

unmatched tiles held. Among

2r+h

remaining tiles,

h

close an open pair and

2r

open a new pair; the latter move fails when

h=2.

Thus

\begin{aligned}F(r,h)&=\frac{hF(r,h-1)}{2r+h}\\&\quad+\frac{2rF(r-1,h+1)}{2r+h},\end{aligned}

omitting the second term when

h=2,

with

F(0,h)=1.

Evaluating this three-state recursion gives

\begin{aligned}F(r,0):\quad&1,\ 1,\ \frac35,\ \frac9{35},\\&\frac3{35},\ \frac9{385}\end{aligned}

for

r=1,2,\ldots,6.

Hence

\frac{p}{q}=\frac{9}{385}

and

p+q=394.