4.6　桶中取黑白球

有一个桶，里面有白球、黑球各100个，人们必须按照以下的规则把球取出来：

1．每次从桶里面拿出来两个球。

2．如果是两个同色的球，就再放入一个黑球。

3．如果是两个异色的球，就再放入一个白球。

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

分析与解法

拿到这个问题的时候，非常多的读者可能会被“100”这个数字吓倒，然后陷入痛苦的思索中。是不是要记录几百次的操作才可能得到结果呢？该怎么处理球的不同组合呢？在分析这种问题的时候，如果仅仅依靠枚举的思路来进行分析，很难得到期望的结果。相反，如果先通过规模比较小的情况（比如假设黑白球各10个、各5个甚至各2个）来进行分析和推断，然后找出其内在的规律，并归纳总结，答题就会比较容易了。

【解法一】

因此，让我们从题目条件出发，先让自己的脑海中浮现出一个大桶，桶里面有白球和黑球各两个，然后开始取球。

为了更好地描述问题，我们可以用一个set（黑球数目，白球数目）来表示桶里面黑球和白球的个数。对于每种球各两个的情况，就可以把桶内黑球、白球表示为（2，2），第一个数表示黑球的数目，第二个数表示白球的数目。如果是从中取出两个黑球，我们可以用（-2，0）来表示黑球数目减少了两个，而白球的数目不变。类似地，（0，-2）用来表示减少了两个白球，而黑球的数目不变。为了方便题目的描述，我们可以通过定义如下的关系来说明对球的操作：

（a，b）＋（x，y）＝（a＋x，b＋y）

（a，b）－（x，y）＝（a-x，b-y）

这样，每次对球的操作，都可以表示为相应的符号操作。

根据获取黑白球的规则，我们可以得到如下推论：

1．由于每次取出两个球之后，均只会放回一个球，那么，每经过一次操作，桶内球的总数会减少一个。也就是说，球的个数肯定会逐步减少，最后减少的规模应该在我们可控的范围之内。

2．从桶中取出两个球之后，只可能是进行下列三种操作之一种：

取出的是两个黑球，则放回一个黑球：（-2，0）＋（1，0）＝（-1，0）

取出的是两个白球，则放回一个黑球：（0，-2）＋（1，0）＝（1，-2）

取出的是黑球白球各一个，则放回一个白球：（-1，-1）＋（0，1）＝（-1，0）

根据上面的规则，对于（2，2）的情况：

第一次操作之后，结果是（1，2）或（3，0）。

第二次操作之后：

对于（1，2）的情况：如果是取两个白球，那么剩下的球为（2，0）；如果各取一个，那么结果为（0，2）。

对于（3，0）的情况：只能取两个黑球，那么结果显然为（2，0）。

第三次操作之后：

对于（2，0）的情况，结果只能为（1，0）。

对于（0，2）的情况，结果同样也只能为（1，0）。

从上面的推断可以看出：

1．每次都会减少一个球，那么最后的结果肯定是桶内只剩一个球。要么是黑球，要么是白球。

2．每次拿球后，白球数量要么不变，要么就是两个两个地减少。

所以从上面的分析可以得出，最后不可能剩余一个白球，那么必然只能是黑球了。

【解法二】

前面的分析似乎过于具体，我们从数学的角度抽象一下，再次回过头来看题目条件：

1．如果是两个同色的球，就再放入一个黑球。

2．如果是两个异色的球，就再放入一个白球。

根据上面两个条件，可以类似地想到离散数学中的异或（XOR）：

两个相同的数，异或等于0。

两个不同的数，异或等于1。

由于当球不同时，就可以再放入一个黑球。那么我们只能把黑球赋值为0，白球赋值为1了。

脑海中浮现的大桶中将不再装着黑球和白球，而是100个1和100个0。

对于每次操作可以做这样的抽象：每次捞出两个数字做一次异或操作，并将所得的结果（1或0）丢回桶中。这样每次操作的过程都不会改变所有球的权值的异或值。

同样可以考虑用比较少的数据来说明这个问题。

假设黑、白球各两个，参数为（2，2），假设操作过程如下：

1．取出两个黑球，放回一个黑球。0 XOR 0＝0，剩下的结果为（1，2）。

2．取出一黑一白，放回一个白球。0 XOR 1＝1，剩下的结果为（0，2）。

3．最后只能取出两个白球。1 XOR 1＝0，剩下的结果为（1，0）。

因为异或满足结合律，即（a XOR b）XOR c＝a XOR（b XOR c），那么上面操作的顺序并不会影响到后面的结果。

从上面的推导中可以看出，取球的过程相当于把里面所有的球进行异或操作，也就是说1 XOR 1 XOR 0 XOR 0＝0。

因此，剩下一个球的时候，桶中的权值等于初始时刻所有球权值的异或值，也就是0。所以剩下一个球的时候一定是黑球。

从上面的解法可以看出，对于复杂问题的分析，最有效的方法就是通过简单的例子进行分析归纳，然后根据实际归纳出的结论进行结果分析。而适当的数学抽象在解决问题的过程中往往有画龙点睛的作用。

扩展问题

1．如果桶中球的个数为黑白各99个，那么结果会怎样？

根据前面的分析，我们已经清楚地知道，可以通过对所有的数字进行异或运算来得到结果，最后异或运算的结果为1。也就是说，最后会剩下一个白球。

同样，我们可以很容易地发现：如果是每种球的个数为偶数，那么最后剩下的一定是黑球；如果球的个数是奇数，那么最后剩下的一定是白球。

2．如果黑白球的数量不定，那么结果又会怎样？

从前面的分析中可以看出，事实上，我们不用太在乎球的数量，只需在乎异或运算的结果就行了。因此，对于球的数目任意的情况，同样只需看最后异或运算的值即可。