Question

有一种单人游戏，规则如下。袋中放有六组各不相同的配对牌。玩家每次从袋中随机抽出一张牌并保留；但只要手中出现一对相配的牌，就立即将这一对放到一旁。如果玩家在任何时刻手中有三张互不相配的牌，游戏就结束；否则继续抽牌，直到袋子为空。袋子最终被抽空的概率为 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 是互质的正整数。求 $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.$

答案

答案：394

知识点：递推概率无放回抽样过程模拟

难度评级：2460

小提示：

记录尚未出现的牌对数 $r$ 和当前手中未配对的牌数 $h$

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

大提示：

从状态 $(r,h)$ 出发，下一张牌要么与手中 $h$ 张牌中的一张配对，要么开启尚未出现的 $r$ 对牌中的一对

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

解答：

设 $F(r,h)$ 为还有 $r$ 对牌尚未出现、手中有 $h\leq2$ 张未配对牌时成功的概率。在剩余的 $2r+h$ 张牌中，有 $h$ 张会闭合一个已开启的牌对，有 $2r$ 张会开启一个新牌对；当 $h=2$ 时，后一种情况会导致失败。因此 $\begin{aligned}F(r,h)&=\frac{hF(r,h-1)}{2r+h}\\&\quad+\frac{2rF(r-1,h+1)}{2r+h}\end{aligned}\text{，}$ 其中当 $h=2$ 时省略第二项，并取 $F(0,h)=1$ 。计算这个三状态递推可得，对于 $r=1,2,\ldots,6$ ， $\begin{aligned}F(r,0):\quad&1,\ 1,\ \frac35,\ \frac9{35},\\&\frac3{35},\ \frac9{385}\end{aligned}\text{。}$ 因此 $\frac{p}{q}=\frac{9}{385}$ ，所以 $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 第 9 题

答案：394

难度评级：2460

小提示：

大提示：

解答：

其他年份的第 9 题