去日本~
みんなは、写真お楽しみに

答案很简单，每个人

1) 先打开标有自己号码的箱子（是箱子的号码不是囚徒的号码）
2) 查看里面的囚徒号码，
3）然后去打开下一个标有与这个囚徒号码相同号码的箱子，如此直到发现自己的囚徒号码或者五十次限制达到为止。

这样做，所有人都找到自己号码的概率大于30%！

---------------------------------

看起来很神奇，为什么呢？首先考虑“把100个号码随机放进100个箱子里”这个动作。这在数学上是称作一个排列(permutation)。以下是一个排列的例子：

箱子号码 1 2 3 4 5 6
囚徒号码 2 4 5 1 6 3

任何一个排列有圈分解，在以上的例子里，1->2->4->1成一个圈，3->5->6->3又成一个圈。于是我们可以把以上这个排列写成(124)(356)。对任何一个排列，总存在唯一的圈分解。有了这个圈分解的概念，我们有如下的事实：

“所有人都找到自己的号码当且仅当这个随机排列里不存在长度大于50的圈。”或者“所有人都被处死当且仅当这个随机排列里存在一个长度大于50的圈。”

于是问题就简化为“一个100长的随机排列里存在一个长度大于50的圈”的概率是多少？为了解决这个问题，我们先给以下这两个引理：

引理1：一个n长的随机排列里有一个n长的圈的概率是1/n

引理2：一个n长的随机排列里有一个m(m<n)长的圈的概率至多是1/m

于是“一个100长的随机排列里存在一个长度大于50的圈”的概率至多是1/51 + 1/52 + ... + 1/100 <= ln(100) - ln(50) = ln 2 = 0.6930 (ln是自然对数）。也就是说，所有人都活着的概率大于1 - ln2 > 30%

-------------------------------------

说了那么多数学，有人会说直观上这到底是怎么回事呢？

这是这题最有意思的地方。事实上，使用这个策略，要么所有人都在50次开箱之内找到自己的号码，要么至少同时有51个人在50次开箱之内都找不到自己的号码。也就是说，不存在有99个人找到号码而只有一个人未找到的情况。相比之下，如果每个人都随机选50个箱子打开，那么当然会出现若干人找不到号码而其它人找到的情况。

也就是说，这个策略的最大用处，在于把概率分布给移位了。对于随机策略，可能出现任何数量的人找到自己的号码；然而使用此策略，则要么所有人都找到，要么至少有51个人都没有找到。这种移位保证了“成功”的概率被放在有意义的地方，而不是出现尽管有若干人找到自己的号码，但仍然全体被杀这样浪费的情况。这种移位是可能的，因为一但号码被随机放进箱子里，这个圈结构就是固定的了。虽然囚徒们不知道这个圈结构具体是什么，但是仍然可以利用它以提高自己活着的概率。

这题以前在math板上出现过，这两天又有人在msn上提了。我重新想了一遍，觉得解法及内在的思路实在是漂亮，特此推荐。

100个囚犯，每人有一个从1到100的不重复不遗漏的号码，国王把这些号码收集起来，打乱放进100个箱子里，每个箱子里有且仅有一个号码。囚犯们一个一个地来到100个箱子面前，每人可以打开至多50个箱子来寻找自己的号码，可以一个一个打开（即可以根据之前箱子里看到的号码来决定后面要打开的箱子）。如果有一个囚犯没有找到自己的号码，那么这100个人一起被处死；只有当所有的囚犯都找到了自己的号码，他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策，但是一但打开了箱子，他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率？

----------------------

显然，每个人随机选50个箱子打开，存活概率会是1/2的100次方，可以小到忽略不计。但是事实上有一种极简单的办法，其存活概率高达30%-_-，大家想一想:)

最近应老板的要求，需要做一些三维图像匹配的算法。上来头一个问题就是如何抽取二维曲面的不变特征以利匹配。给一张高度图，我们当然可以用图像上的算法（比如说SIFT）来完成任务，不过如果有三维旋转不变的特征，总是会更好些。

我第一个想到的是微分几何的方法，面法线及主副曲率方向构成了一个局部的三维标架，对齐这个三维标架就相当于达到了旋转不变的要求。想法很清楚，不过找一个求主曲率方向(principal direction)的算法却花了整整一天的时间，虽然曲率值的公式遍地都是。以往我们最好的朋友google这回完全不灵了，Wiki和Mathworld要么只给high-level idea，要么只有不知所云的相关公式。我相信教科书上或者长年做graphics的同学们一定知道，不过今天是周日，谁会高兴和人讨论这种问题呢？而我，为了即将到来的日本之行，这两天还是多干点吧-_-。

微分几何我还曾是认真地学过的呢，想不到真要上手了，还是完全不行。不摸键盘不动纸笔，概念总是很模糊的，脑中那些抽象的“形式”，也就只能拿来唬人；直到火烧眉毛要上了，才会真正地理解。

由此我想说，并不是一切都能用google来解决，它最多给一些现成的结果，而且还可能是错的。最好的状态是先学过大概（然而必须要正确的）概念框架，然后以google来作局部纠正，并引导新思路的产生。如果没有概念或者概念错误，那么只会越看越糊涂，特别像微分几何这种现代表述和经典表述并立，张量记号和向量矩阵记号并行的，特别容易出问题。我所花的大部分时间，都是在几个结论里来回犹豫，不知应该看哪个好，并因此而感到十分烦躁（我的经验是google的作用只能持续二十分钟到半小时，之后如果没有决心，往往就放弃了）。最后还是下决心把微分几何里的第一和第二基本形式复习了一遍，才知道应该怎么做，并且纠正了Wiki和Mathworld上的错误各一。

好久没看数学书了，静一静心，重新开始吧。