先手还是后手：抽到红球获胜

To Begin or Not to Begin?

专题: Strategy / 策略
难度: L4
来源: QuantQuestion

题目详情

An urn contains k black balls and a single red ball. Peter and Paula draw without replacement balls from this urn, alternating after each draw until the red ball is drawn. The game is won by the player who happens to draw the single red ball. Peter is a gentleman and offers Paula the choice of whetherl she wants to start or not. Paula has a hunch that she might be better off if she starts; after all, she might succeed in the first draw. On the other hand, if her first draw yields a black ball, then Peter's chances to draw the red ball in his first draw are increased, because then one black ball is already removed from the urn. How should Paula decide in order to maximize her probability of winning?

解析

总共有 $k$ 个黑球和 1 个红球，共 $k+1$ 个球。

把过程等价为：两人轮流把球取出（不看颜色）直到取完，最后谁拿到红球谁赢。赢家与原游戏一致。

若 $k$ 为奇数，则 $k+1$ 为偶数，两人各取 $(k+1)/2$ 个球，因此红球落在任一方手里的概率都是 $1/2$ 。
若 $k$ 为偶数，则 $k+1$ 为奇数，先手会比后手多取 1 个球：先手取 $k/2+1$ 个，后手取 $k/2$ 个，因此先手胜率为

\frac{k/2+1}{k+1}=\frac{k+2}{2k+2}.

因此 Paula 的最优选择是： $\boxed{总是先手}$ （ $k$ 偶数时严格更有利， $k$ 奇数时不吃亏）。