桶中取黑白球

《编程之美》4.6读书笔记

问题：

有一个桶，里面有白球和黑球各100个，规则如下：

1. 每次随机从桶中取出两个球
2. 如果是两个同色的球，就再放入一个黑球
3. 如果是两个异色的球，就再放入一个白球

问：最后桶中只剩下一个黑球的概率是多少？

解法：

刚拿到这个问题，我的第一个想法就是用程序来计算各种情形出现的概率，然后再用递归求出最终的结果，不过可能因为程序存在一个bug，结果一直得到的是一个错误的结果

下面列出作者给出的正确解法，看来思维僵化实在太可怕了！

解法一：

我们可一个用一个set（黑球数量， 白球数量）来表示桶中的黑球和白球的个数。从桶中取出球后，只可能是下列三种操作：

1. 取出的是两个黑球，则放回一个黑球：（-2， 0） + （1， 0） = （-1， 0）
2. 取出的是两个白球，则放回一个黑球：（0， -2） + （1， 0） = （1， -2）
3. 取出的是一黑一白，则放回一个白球： （-1， -1） + （0， 1） = （-1， 0）

根据上面的规则，我们可以发现：白球的数量变化情况只能是不变或者-2，也就是说，如果是100个白球，白球永远不可能是1个的情况，那么问题的解法就很简单了，就是概率为0

解放二：

通过上面的分析，我们可以看出这样的规则和xor操作很形似，可设黑球为0， 白球为1

就有可能是0 xor 1 xor 1 ……之类的情况，又因为异或满足结合律，上式可变为：

（0 xor 0 …… xor 0） xor （1 xor 1 …… xor 1）两边都是100个，结果就是0

扩展结论：

由最后的xor式子， 我们就可以看出，最后的结构完全由白球的数量来决定，如果白球的数量为偶数，概率为0，否则为1