@爱狗却养猫 #2 另外，什么是XKCD？

前面回答的表乱了，重新贴一下：

海盗编号/p100的金币/p99的金币/p98的金币/p97的金币/p96的金币/p95的金币/p94的金币/p93的金币..... p100/50 p99/0/50 p98/0/0/50 p97/1/1/0/48 p96/2/0/1/0/47 p95/0/1/2/1/0/46 p94/1/2/0/0/1/0/46 p93/2/0/1/1/0/1/0/45 ...

前面回答的表乱了，重新贴一下：

海盗编号/p100的金币/p99的金币/p98的金币/p97的金币/p96的金币/p95的金币/p94的金币/p93的金币.....

p100/50

p99/0/50

p98/0/0/50

p97/1/1/0/48

p96/2/0/1/0/47

p95/0/1/2/1/0/46

p94/1/2/0/0/1/0/46

p93/2/0/1/1/0/1/0/45 ...

先不考虑1.2和2.2，关于第一题的我的思路如下：

100个犯人讨论选出一个特别犯人，最终做出“所有人都被审讯过”的陈述的那个犯人也是他，我们把他记作1号犯人。因为审讯是完全随机的，所以并不知道1号犯人什么时候开始被审讯，不过没关系，1号犯人第一次被带去审讯室之前的所有审讯都不考虑。从1号犯人第一次被带去审讯室开始，他把灯打开。然后其他犯人被带入审讯室时，如果发现灯是亮的就把灯关掉，如果发现灯是关的就不要做任何操作。对于其他所有犯人来说，只有在第一次发现灯是亮的的时候把它关掉，之后再发现就不要做任何操作。

然后1号犯人开始计数，从他第一次打开灯开始，每当发现有人关掉了灯，就计数+1，同时再把关掉的灯打开。重复操作直至计数达到99，这意味着有99个犯人关过他开的灯，又因为每个犯人只能关一次灯，所以证明其他99人均已到过审讯室。在他第99次发现有人关掉他的灯的时候，他便可以放心的宣称：“所有人都已至少被审讯了一次。”

第二题思路：

这题的解法比较投机取巧，只能在绝对理想的条件下成立，现实中永远无法成立。目前有100个海盗，我们先简化该题试试看。先假设前面98个海盗都因为提案不被通过而被处决，只剩下最后两个海盗p99和p100，我们看看会发生什么。这个时候p99需要提供提案，p100来投票，这个情况就非常简单了，p99无论如何提案，p100都会无情否决，因为否决之后所有金币都是自己的了，同时又因为题干中给出“每个海盗的优先级为：首先活着，然后得到尽可能多的金币，最后希望尽可能多的其他海盗被杀。”所以就算p99的提案是把所有金币都给予p100，p100仍然会否决该提案，杀死p99。

现在我们再假设前面97个海盗都被投票处决了，只剩p98，p99和p100。p98需要提案。这时候p99的想法是，如果p98的提案被否决，轮到我提案我就死定了（参考上一段），所以无论p98如何提案，p99都会全力赞同，所以p98至少能拿到一半的投票支持，无论什么提案都会被通过。那么p98的提案当然是自己拿全部的金币，p99和p100拿0个金币。

现在我们再假设前面96个海盗都被投票处决了，只剩p97，p98，p99和p100。p97需要提案并得到至少两个支持。这时候p98的想法是，搞死p97我就赚大了（参考上一段），所以他一定投反对票。p99的情况比较特殊，按照题干描述他想多弄死一个海盗，但是如果有钱拿，他就会去拿钱。如果p98提案，p99为了自保一个金币也拿不到，这时如果p97可以给p99一个金币，就可以确保p99投票给他。p100的情况也比较特殊，他也想多弄死一个海盗p97，但在p98的提案中（参考上一段）他是一个金币也没有的，所以只要p97给他一个金币，他就马上转向支持他。所以p97的最优提案是：p98得到0个金币，p99得到1个金币，p100得到1个金币。

不断向前推，我们便可以得到下表： 海盗编号/p100的金币/p99的金币/p98的金币/p97的金币/p96的金币/p95的金币/p94的金币/p93的金币..... p100 /50 p99 /0 /50 p98 /0 /0 /50 p97 /1 /1 /0 /48 p96 /2 /0 /1 /0 /47 p95 /0 /1 /2 /1 /0 /46 p94 /1 /2 /0 /0 /1 /0 /46 p93 /2 /0 /1 /1 /0 /1 /0 /45 ...

依此方法逆推便可发现海盗p(n)的提案的规律是：自己留下金币数为50 - roundup((100-n)/2)，剩余的钱散发给后面的海盗以获得过半支持率。roundup()的意思是向上取整。（这个公式只对p99无效，因为他死定了。） 那么p1海盗的最优提案为：自己留下0个金币，50个金币全部发出去以求过半支持率保证自己存活。

This scene really made me recall "too young too simple, sometimes naive...." :D :D :D