# 毎日一题 -  桶中取黑白球

## 信息卡片

* 时间：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；


## 优秀解答

>暂缺
