Question

Se juega un solitario de la siguiente manera. Se colocan en una bolsa seis pares distintos de fichas iguales. El jugador extrae fichas al azar, una por una, y las conserva, excepto que un par de fichas iguales se aparta tan pronto como aparece en su mano. El juego termina si el jugador llega a tener tres fichas sin que haya dos iguales; de lo contrario, continúa sacando hasta vaciar la bolsa. La probabilidad de vaciar la bolsa es $\frac{p}{q},$ donde $p$ y $q$ son enteros positivos coprimos. Halla $p+q.$

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.$

Respuesta

Respuesta: 394

Conceptos:probabilidad recursiva muestreo sin reemplazo simulación de procesos

Nivel de dificultad: 2460

Pista pequeña:

Registra el número $r$ de pares aún no vistos y el número $h$ de fichas sin pareja que se tienen en la mano

Track the number $r$ of unseen pairs and the number $h$ of unmatched tiles currently held

Pista grande:

Desde el estado $(r,h)$ , la ficha siguiente empareja una de las $h$ fichas en la mano o abre uno de los $r$ pares aún no vistos

From state $(r,h)$ , the next tile either matches one of the $h$ held tiles or opens one of the $r$ unseen pairs

Solución:

Sea $F(r,h)$ la probabilidad de éxito cuando quedan $r$ pares aún no vistos y se tienen $h\leq2$ fichas sin pareja. Entre las $2r+h$ fichas restantes, $h$ cierran un par abierto y $2r$ abren un nuevo par; este último caso produce una derrota cuando $h=2.$ Por tanto, $\begin{aligned}F(r,h)&=\frac{hF(r,h-1)}{2r+h}\\&\quad+\frac{2rF(r-1,h+1)}{2r+h},\end{aligned}$ donde se omite el segundo término cuando $h=2,$ y $F(0,h)=1.$ Al evaluar esta recurrencia de tres estados se obtiene $\begin{aligned}F(r,0):\quad&1,\ 1,\ \frac35,\ \frac9{35},\\&\frac3{35},\ \frac9{385}\end{aligned}$ para $r=1,2,\ldots,6.$ Por consiguiente, $\frac{p}{q}=\frac{9}{385}$ y $p+q=394.$

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.$

1994 AIME Problema 9

Respuesta: 394

Nivel de dificultad: 2460

Pista pequeña:

Pista grande:

Solución:

El Problema 9 en otros años