A Practical Guide To Quantitative Finance Interviews 收录了一些量化面试中的经典题目. 本文介绍的是来自第二章的「Last Ball」.

Last Ball #

Problem #

A bag has 20 blue balls and 14 red balls. Each time you randomly take two balls out.(Assume each ball in the bag has equal probability of being taken). You do not put thesetwo balls back. Instead, if both balls have the same color, you add a blue ball to the bag;if they have different colors，you add a red ball to the bag. Assume that you have anunlimited supply of blue and red balls, if you keep on repeating this process, what willbe the color of the last ball left in the bag? What if the bag has 20 blue balls and 13 redballs instead?

Solution #

可能的变化情况有三种:

• BB→B: $N_B$ 减 $1$, $N_R$ 不变
• RR→B: $N_B$ 不变, $N_R$ 减 $2$
• BR→R: $N_B$ 减 $1$, $N_R$ 不变

由于每次操作都会在使得球变少的同时保持 $N_R$ 的奇偶性不变, 因此最终留下的球的颜色只取决于初始 $N_R$ 的奇偶性. 在本题中, $N_B = 20, N_R = 14$ 时, 最终剩下的球为蓝色; $N_B = 20, N_R = 13$ 时, 最终剩下的球为红色.