67 lines
2.7 KiB
Markdown
67 lines
2.7 KiB
Markdown
# 毎日一题 - 桶中取黑白球
|
||
|
||
## 信息卡片
|
||
|
||
* 时间：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；
|
||
|
||
|
||
## 优秀解答
|
||
|
||
>暂缺
|