leecode/daily/2019-08-21.md

毎日一题 - 桶中取黑白球

信息卡片

• 时间：2019-08-21
• tag：Math 位运算

题目描述

有一个桶，里面有白球，黑球各100个，你必须用以下规则将球取出来：
- 每次从桶里取两个球
- 如果两个球是相同的颜色，那么再放一个黑球
- 如果两个球是不同的颜色，那么再放一个白球。
问：最后一个球是黑球的概率是多少？

参考答案

1. 数学分析原问题

首先我们来仔细读题看看我们有哪些知道的信息：

• 不管什么情况，每次球的总数减1；
• 两黑：黑球-1，白球0；
• 两白：黑球+1，白球-2；
• 一黑一白：黑球-1，白球0；
• 最后两球只要不是一黑一白，最后一球都是黑；

初始状态是100个黑球和100个白球，从上面三个状态可知道，黑球要么+1要么-1，而白球要么不变要么-2；在198次取球后，我们可知剩余两个球，现在假设剩余的两球为一黑一白，可以证明这是不存在的。

因为白球下降是以2的倍数下降，不可能从100下降至1,；故剩余两球肯定不是一黑一白的情况，那么最后一球的情况必然为黑。

2. 原问题拓展（n个黑球和m个白球）

在n+m-2次取球后，剩余两个球。

由于我们知道白球数下降是以2的倍数下降，如果m为偶数的话，是不可能下降至1；即同上1，最后一球必为黑球。如果m为奇数的话，最后必然是k黑1白（k>=1），显然对于任意的k，要么剩余全是黑球，要么黑球不断减1，最后变为1黑1白。全黑和1黑1白最后的结果都是剩余一个白球。

得出结论，最后一球结果无关黑球数量（n>=0）,仅与白球数量m有关。

• 如果白球m为奇数，最后一球必然白；
• 如果白球m为偶数，最后一球必然黑；

3. 抽象为数学模型，严格证明

不妨设黑球为0，白球为1；

• 两黑：F(0,0) = 0；表示两个黑球生一黑；
• 两白：F(1,1) = 0；表示两个白球生一黑；
• 一黑一白：F(0,1) = 0；表示一个黑球一个白球生一白；

仔细观察就会发现这个函数F就是XOR（异或）；

那么m个黑球和n个白球，就抽象为m个0和n个1作异或的结果；而且我们可知异或满足结合律和交换律（证明略，最简单的证明方法枚举）。

那么问题就很简单，对于任意多0，异或结果依然是0，所以对于任意多1，只需要考虑1个数的奇偶性就可判断最后剩余1个1还是0个1；

结论同2：

• 1（白球）的个数奇数，最后异或结果为1；
• 1（白球）的个数偶数，最后异或结果为0；

优秀解答

暂缺