上网查资料的时候偶然间看到一道百度的面试题,题意大概如下:

一个桶,100个黑球100个白球,每次取走两个球,如果同色则放入一个黑球,如果异色则放入一个白球。求最后只剩下一个黑球的概率。

思考过程:

一、首先排除了计算机模拟的思路,因为最后答案要求的概率,计算机模拟出的都是频率,所以这个方法肯定行不通,kill。

二、用算,当然肯定希望每次取的概率能够累加化简,做了一会儿,发现貌似不行,而且仔细一想,这不是数学题,不可能考排列组合数的计算,所以kill。

三、题目有特点,对称形式,黑球和白球的数量相同,取走放入方法相似(同色放黑球,异色放白球,初始时同色异色的概率相同),这样,答案只可能有三种:0、1、0.5,没谁了。

解题过程:

正推,分支太多,计算量太大。正难则反,逆推。如果最后要剩下一个黑球,只可能是取走两个同色球(2黑或2白),再放入一球(黑),所以,是不是所有的情况都可以化为这两种情况(2黑或2白)。待定。

寻找取球的本质,一共三种取球方式:

球的变化
1.取走2白 再放入1黑 2白换1黑
2.取走2黑 再放入1黑 取走1黑
3.取走1黑1白 再放入1白 取走1黑

虽然球是这么多,但是肯定是化归成2白或2黑的形式,或者说最后肯定会化归成1黑的形式。

不能被球的数量干扰,试着去探索题目的本质,答案似乎很接近了。

正解:

如果是取2白,最后会全部变成黑球,最后只剩1黑;

如果是取2黑,最后会剩1黑,白球不变。接下来:一、如果取2白,最后全部变成黑球,最后只剩1黑;二、如果取1黑1白,等效于取走1黑,最后只剩黑球,最后只剩1黑。

如果是取1黑1白,再放入1白,等效于取走1黑,最后只剩白球。只能全部取白球,最后全部变成黑球;或者1黑1白地取,最后也是化归为全白,最后只剩2白,最后只剩1黑。

所以概率为1。

推广:

根据化归的思路,很容易推广至一般情况:

如果白球的个数是奇数(黑球数量同白球),则只剩1白球;

如果白球的个数是偶数(黑球数量同白球),则只剩1黑球。