战争中你被俘了，敌人拷问你情报。你是这么想的：如果我把情报都告诉他们，他们就会认为我没有价值了，就会杀了我省粮食，但如果我死活不说，他们也会认为我没有价值而杀了我。怎样才能做到既让他们确信我知道情报，但又一丁点情报也不泄露呢？

这的确是一个令人纠结的问题，但阿里巴巴想了一个好办法，当强盗向他拷问打开山洞石门的咒语时，他对强盗说：“你们离我一箭之地，用弓箭指着我，你们举起右手我就念咒语打开石门，举起左手我就念咒语关上石门，如果我做不到或逃跑，你们就用弓箭射死我。”

强盗们当然会同意，因为这个方案不仅对他们没有任何损失，而且还能帮助他们搞清楚阿里巴巴到底是否知道咒语这个问题。阿里巴巴也没损失，因为处于一箭之地的强盗听不到他念的咒语，不必担心泄露了秘密，而且他确信自己的咒语有效，也不会发生被射死的杯具。

强盗举起了右手，只见阿里巴巴的嘴动了几下，石门果真打开了，强盗举起了左手，阿里巴巴的嘴动了几下后石门又关上了。强盗还是有点不信，说不准这是巧合呢，他们不断地换着节奏举右手举左手，石门跟着他们的节奏开开关关，最后强盗们想，如果还认为这只是巧合，自己未免是个傻瓜，那还是相信了阿里巴巴吧。

“零知识证明”说的是示证者向验证者表明他知道某种秘密，不仅能使验证者完全确信他的确知道这个秘密，同时还保证一丁点秘密也不泄露给验证者。阿里巴巴的这个方案，就是认证理论“零知识证明”的一个重要协议。

除了被俘后如何靠情报保命这个问题，零知识证明在社会领域中还有着很多应用场合。例如你证明了一个世界级的数学难题，但在发表出来之前，总是要找个泰斗级的数学家审稿吧，于是你将证明过程发给了他，他看懂后却动了歪心思，他把你的稿子压住，把你的证明用自己的名义发表，他名利双收，你郁闷至死，你去告他也没用，因为学术界更相信的是这位泰斗，而不是你这个无名之辈。

Read the rest of this entry »

4条腿长度相等的椅子放在起伏不平的地面上，问是否一定可以找到一个位置使得四条腿同时着地而放稳？

这个问题我在初中的时候就听赵一夫跟我说起过，当时觉得这问题太诡异了，怎么下手啊。今天再一次见到仍然觉得无从下手，看了答案之后顿觉奇妙。答案是肯定的，一定可以找到一个位置使得椅子放稳！

题目的条件先解释一下，4条腿长度相等实际上告诉了我们这4条腿的顶点是共面的。看了网友的回复，确实题目里有隐含条件需要明确地写出来：（1）椅子是正方形的…（2）四条腿的长度相对于地面的起伏来说足够长…(3)只要四条腿同时着地就称之为放稳（即认为地面的摩擦系数无穷大）…（4）起伏不平的地面我们要把它理解成是一个连续的二元函数。

Read the rest of this entry »

/*这篇文章的主要内容由热学欧阳颀老师所讲 出自某期New York Times*/

下面要进行的一段推导，将十分诡异，可能有点莫名其妙的感觉，不过还是请完整看下去~
首先说一下什么是哥白尼原理。

Copernican principle:
The best theories are those that do not require the observer to live in a special place in the universe or at a special time in history in order to be true.

也就是说，一个好的理论必须满足，我们既不在宇宙中的一个特殊位置，也不处在一个特殊的时间。这个原理我想大家都可以承认吧。

为了热身，我们先推导一下柏林墙倒塌的时间。

柏林墙于1961年建立，而原文章作者Dr. Gott偶然地于1969年去了一趟柏林墙，此时柏林墙已经存在了8年。

上图中，第一行整体表示柏林墙从建立到最终倒塌的整个生命历程。其中中间50%被染成紫色，这个50%是作者自己设定的，他将给出一个时间区间，而柏林墙倒塌的时间在这个区间里面的概率为50%。

根据哥白尼原理，作者访问柏林墙的这个事件是完全随机的，它落在上图第一条线段上任何一个点的概率是均匀分布的，因此这个点落在紫色区域的概率是50%，也就是说，他去访问柏林墙的时间点处在柏林墙整个生命历程的25%~75%之间的概率是50%。

若他访问的时刻位于第二条直线上的Now位置，也就是说，处于柏林墙生命历程的25%处，那么由此推算，柏林墙的寿命将还有24年（8年占25%，则剩下75%代表24年）。

若他访问的时刻位于第三条直线上的Now位置，也就是说，处于柏林墙生命历程的75%处，那么可以算出，柏林墙的剩余寿命将只有8/3年（8年占了75%，剩下的25%只有8/3年）。

因此，他访问的时刻位于紫色区域时，推算出的柏林墙剩余寿命是在8/3年~24年之间的，因此他声称，柏林墙在未来8/3~24年内倒塌的概率是50%。

当然他也可以把一开始的概率设置成60%或者其他数字，这样将推算出来另一个时间区间，柏林墙生命历程终止于这个新时间区间的概率将为60%。

最终，柏林墙于1989年倒塌。其实，作者写这篇文章的时候已经是90年代了…

下面，他又用同样的方法，给出了人类文明灭亡时间的推算。

Read the rest of this entry »

在SF神牛的鼎力推荐下看完了日剧《欺诈游戏》（Liar Game），大赞其游戏设计之强大，尤其是其中的“少数决”游戏。按照SF神牛的说法，看了这个日剧以后会觉得其他的博弈游戏都黯然失色…下面内容转载自http://www.matrix67.com/blog/archives/2591

  欺诈游戏的第二场共有22人参加。这22个人集中在一个阴森的大厅里，参加一个叫做“少数决”的游戏。游戏规则很有意思：主办方随机抽取一个人到台上来，向众人问一个二选一的问题，比如“你信春哥吗”。每个人手里都会得到两张选票，两张选票上都印有自己的名字，但其中一张纸上印有“YES”，另一张纸上印有“NO”。游戏者们有6个小时的时间进行交流和考虑，并要在时间结束前将自己的选择投入投票箱。时间结束后，主办方进行唱票，并规定票数较少的那一方取胜，多数派将全部被淘汰。获胜的选手将进行新一轮的游戏，主办方从剩下的人中重新选一位进行提问，并要求大家在6个小时内投票，唱票后仍然宣布少数派胜出。若某次投票后双方人数相等，则该轮游戏无效，继续下一轮。游戏一直进行下去，直到最后只剩下一人或两人为止（只剩两人时显然已无法分辨胜负）。所有被淘汰的人都必须缴纳罚金，这些罚金将作为奖金分给获胜者。
    这个游戏有很多科学的地方，其中最有趣的地方就是，简单的结盟策略将变得彻底无效。如果游戏是多数人获胜，那你只要能成功说服其中11个人和你一起组队（并承诺最后将平分奖金），你们12个人便可以保证获胜。但在这里，票数少的那一方才算获胜，这个办法显然就不行了。因此，欺诈和诡辩将成为这个游戏中的最终手段。如果你是这22个参赛者中的其中一个，你会怎么做呢？

Read the rest of this entry »

今天六一，这个曾经属于我们的节日。岁月无情的在我日渐苍老的脸上刻上了印记，看到照片上小时候稚嫩的我，看到肯德基里面孩子们无忧无虑欢乐的笑脸，我总有种莫名的感伤。今天写下几句小的数学娱乐，来祭奠逝去的似水年华。虽然我们不能企图永远年轻，但至少可以像小孩子那样笑颜永驻。

1.我已经证明了著名的数学难题：任何一个偶素数总能写成两个奇数之和。
2.对于这个数学难题：方程n^a+n^b=n^c对于n>2没有正整数解，我已经找到了一个极其简单的证明，甚至一页之内就能搞定。
3.我已经想到了一个绝妙的宇宙万能公式，只不过这里空白太小，写不下…(这句话曾经是我的校内网状态和QQ个性签名，用在有字数限制的地方特别合适)
4.原来任何进制都是10进制..
5.世界上有10种人，一种是懂二进制并且看贴回贴的人，一种是不懂二进制或者看贴不回帖的人…

Read the rest of this entry »

昨天去图书馆看趣味数学大师马丁加德纳的小册子《意料之外的绞刑》，看到了这个趣题：求两圆柱相交部分的体积（两圆柱半径都为1）（正交）。要求是不用微积分，只用高中生就能看懂的简单数学。如果你难以想象那部分到底是个什么形状，下面这幅图可以帮帮你。

Read the rest of this entry »