Puzzles

http://www.rowkey.me/blog/2018/01/04/king-rec-pois-wine/

国王有一百桶酒，比自己的生命还重要。结果有一天其中一桶被投了慢性毒药，喝了以后半个小时以后就会死掉。国王大怒，命令玩忽职守的侍卫去试毒。酒不能被混合，一个侍卫可以喝多桶酒，一桶酒也可以由多个侍卫喝，怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。侍卫可以理解为线程，即怎么样用最少的线程用最快的速度完成这个工作。

此问题是我在面试时经常用的一道题目，主要考察的是候选人能不能以计算机的思维考虑问题。

最简单的方案肯定是找100个人，每个人试一桶酒，那么用时30分钟，就可以判断出哪一桶就有毒。

再进一步的，可以使用分段法，把酒分成n份，先找n个侍卫试酒，可以定位出哪一段的酒有毒，再接着分段试酒。但这种方案，分段数目越少，试出毒酒的平均耗时就越长。

如果用计算机的思维来分析这个问题，那么首先考虑如何存储这100桶酒。100桶酒可以用二进制7个bit来表示（27>100）。对应那一桶毒酒，其二进制表示中为1的位置如果能够可以定位出来，就可以定位出此桶毒酒。可以找7个侍卫编号1-7。对于每一桶酒的二进制表示（不足七位前面用0表示），从第一位到第七位，如果是1，则对应编号的侍卫喝此桶酒。这样，每个侍卫喝掉对应的酒。30分钟后，侍卫按照编号1-7，死掉的置为1，活着的置为0，如此，侍卫的一个序列如0000111就表示第七桶酒为毒酒。

上述最后一种方案提现了在计算机中使用bit来解决问题的思路。当需要节省存储的时候，使用bit来做经常会有出其不易的效果。就比如最近很火的电影《天才枪手》中，主角们记忆选择题的答案A、B、C、D，完全可以使用位编码来表示四种答案:00-A 01-B 10-C 11-D，四个bit转换为一个十六进制数字，如此就可以节省一半的存储，记忆起来也会简单很多。此外，我们处理大数据去重/计数使用的Bitmap、BloomFilter，也都是一种使用bit节省存储的思路。

三门问题（蒙提霍尔问题）

参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车或者是奖品，选中后面有车的那扇门就可以赢得该汽车或奖品，而另外两扇门后面则各藏有一只山羊或者是后面没有任何东西。当参赛者选定了一扇门，但未去开启它的时候，知道门后情形的节目主持人会开启剩下两扇门的其中一扇，露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。问题是：换另一扇门会否增加参赛者赢得汽车的机会率？

以上问题描述摘自维基百科。

首先有一点可以明确：如果参赛者不更换的话，那么他选中汽车的概率是1/3,这与主持人做了什么完全无关。所以我们现在要考虑的是参赛者会更换选择的情况，也就是说，我们假定参赛者在主持人开门后一定会更换选择。

https://www.guokr.com/post/9314/

　　问题的答案是可以：当参赛者转向另一扇门而不是继续维持原先的选择时，赢得汽车的机会将会加倍。 　　有三种可能的情况，全部都有相等的可能性（1/3）： 　　参赛者挑山羊一号，主持人挑山羊二号。转换将赢得汽车。 参赛者挑山羊二号，主持人挑山羊一号。转换将赢得汽车。 参赛者挑汽车，主持人挑两头山羊的任何一头。转换将失败。 在头两种情况，参赛者可以透过转换选择而赢得汽车。第三种情况是唯一一种参赛者透过保持原来选择而赢的情况。因为三种情况中有两种是透过转换选择而赢的，所以透过转换选择而赢的概率是2/3。 　　如果没有最初选择，或者如果主持人随便打开一扇门，又或者如果主持人只会在参赛者作出某些选择时才会问是否转换选择的话，问题都将会变得不一样。例如，如果主持人先从两只山羊中剔除其中一只，然后才叫参赛者作出选择的话，选中的机会将会是1/2。 　　还可以用逆向思维的方式来理解这个选择。无论参赛者开始的选择如何，在被主持人问到是否更换时都选择更换。如果参赛者先选中山羊，换之后百分之百赢；如果参赛者先选中汽车，换之后百分之百输。而选中山羊的概率是2/3，选中汽车的概率是1/3。所以不管怎样都换，相对最初的赢得汽车仅为1/3的机率来说，转换选择可以增加赢的机会。

当然也有异议者提出50%
人们给出的答案是2/3，当然这个是错误的。 　　2/3是怎么来的？我来给大家解释一下： 　　第一个人第一次选的门，是车的概率是1/3， 　　第二个人打开一张门后，车肯定是在剩下的两张门中， 　　所以最后一张门的几率是1-1/3=2/3。 　　这个想法和解释是完全错误的。 　　错误在哪？ 　　“第一个人选的第一个门的几率是1/3” 这个错了。 　　1/3这个几率是在样品个数为3的情况下得出的。 　　当第二个人打开另一张门的时候，整个事件的样品个数为2。 　　当第一个人不改变选择的时候，其实他已经选择了第二次！ 　　他选择的是“不变”，不代表他的几率“不变” 　　整个事件的过程如下： 　　一个人选了一张门，不打开。 　　另一个人在剩下的两张门中，选出一张后面是羊的门。 　　第一个人在剩下的两张门中再次选择了第一次选择的门。 　　所以，他选到车的概率为50%。

很老的问题了，不过在任何时候都能引起激烈的争论，更神奇的是无论直觉派，概率派等都认为自己的答案有道理。维特根斯坦认为世界上多数问题归根结底都是语言问题。三门问题的争论其实也是语义上的。正确答案应该是： 　　如果主持人事先知道哪个门里有山羊并且他特意选择了有山羊的门打开了，那么参赛者应该换另一扇门，这可以将他胜利的概率从1/3升到2/3。 如果主持人事先不知道哪个门里有山羊或者他只是随机的选择了一个门，但事实发现里面恰好是山羊。这时候参赛者没有换门的必要，胜利概率总是1/2。 　　也就是说，概率产生的根本在于这到底是一个人为操作的事件，还是一个纯随机的数学事件。