题目
有一个桶,里面有白球、黑球各100个,现在按下述规则取球:
每次从桶里面拿出来两个球;
如果是两个同色的球,就再放入一个黑球;
如果是两个异色的球,就再放入一个白球。
问:最后桶里面只剩下一个黑球的概率是多少?
解题思路
根据条件2和3,可以类似地想到数学中的异或(XOR):
两个相同的数,异或等于0;
两个不同的数,异或等于1。
由于当球不同时,就可以再放入一个黑球。那么我们只能把黑球赋值为0,白球赋值为1。
这样可以想象大桶中包含100个0和100个1。
每次取球可以抽象为,两个数字做一次异或操作,并将所得的结果(1或0)丢回桶中。这样每次操作过程都不会改变所有球的权值的异或值。
假设黑、白球各两个,参数为(2,2),操作过程如下:
取出两个黑球,放回一个黑球。0 XOR 0 = 0,剩下的结果为(1,2)。
取出一黑一白,放回一个白球。0 XOR 1 = 1,剩下的结果为(0,2)。
最后只能取出两个白球。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. 如果黑白球的数量不定,那么结果又会怎样?
事实上,我们不用太在乎球的数量,只需在乎异或运算的结果就行了。因此,对于球的数目任意的情况,同样只需看最后异或运算的值即可。