刚刚看到一道智力题，颇有些意思，说来给大家听听。我把题意稍微改了一下，原题中的 XX 侠是一个（不太容易解释的） lynch mob 。
某座城市里发生了一起命案，已经确定凶手是 8 个嫌疑犯之一。经过很多可靠的调查，城南和城北的两名警探各自独立地把嫌疑犯的名单缩减到了两个人。现在，两名警探正在通电话，他们试图对比一下彼此的调查结果。如果他俩的嫌疑犯名单中正好只有一处重合，他们就能确定出凶手的身份了。但问题是，这座城市里有一个伸张正义、凌驾于法律之上的 XX 侠，他正在窃听两名警探的通话。如果他从中获知了凶手的身份，他将在警方实施拘捕之前先杀死凶手。
现在， XX 侠已经知道了那 8 个嫌疑犯是谁，但不知道两名警探各自都把目标锁定在了哪两个人上。这两名警探之前从未见过面，这通电话是他们俩第一次进行交流。他们俩能成功地确定凶手的身份，而又不让 XX 侠知道凶手是谁吗？
（当然，这里我们不允许使用那些基于数论的公钥加密体系，不然题目就没啥意思了）
经典 Geek 动画 Futurama 上周播出了第 6 季的第 10 集 The Prisoner of Benda 。在这一集中，教授 Farnsworth 发明了一种“心灵对换机”，它可以把两个人的思想互相对换，使得 A 的大脑跑进 B 的身体里，而 B 的大脑则跑到 A 的身体里。 Farnsworth 和 Amy 都想得到对方的身体，便成为了这台机器的第一对实验者。等到他们爽够了想换回来后， Farnsworth 却发现了一个严重的问题：已经互换过大脑的两个身体不能再次进行大脑对换操作。但这并不表示两个人完全没有希望回到自己的身体里—— Farnsworth 突然想到，或许可以用第三者作为一个临时的大脑储存空间，从而实现间接对换。正巧机器人 Bender 进了实验室，于是（身为 Amy 的） Farnsworth 和 Bender 又坐上了机器，这下 Farnsworth 的大脑便跑到 Bender 身体里了，而 Bender 的大脑则进了 Amy 的身体里。此时 Farnsworth 才意识到，引入一个第三者是不够的——再让（身为 Bender 的） Farnsworth 和（身为 Farnsworth 的） Amy 互换大脑，可以让 Farnsworth 恢复原状，但同时 Amy 的大脑会跑到 Bender 的身体里去；这样 Bender 和 Amy 的身体正好颠倒了，而他们却已不能再次使用机器。换句话说，要想恢复两个换位了的大脑，需要引入不止一个新的人。
但现在，问题已经变得更加复杂了——这下已经产生了三个大脑位置错乱的人。大家很容易联想到一个更一般的问题：给定 n 个人以及他们之前使用“心灵对换机”的记录，至少得引入多少个新的人，才能让所有人的大脑都“物归原主”呢？
完美的制度是永远不存在。我们可能会产生一种觉得某某制度很完美的错觉，这只是因为我们习惯了它而已。若把这个制度拿出来仔细琢磨琢磨，你会发现它还存在太多的问题。
我们习惯了“多数票当选”的选举制度。每个投票者把自己手中的票投给其中一位候选人，得票数最多的候选人即获胜，因为他的支持者最多。这看上去似乎挺合理。但在实际生活中，这种选举制度并不见得总是合理的——得票数最多的候选人很可能并不是大家喜欢的候选人。有时候，获胜的候选人竟会是最不受欢迎的那个人。
假设有 A 、 B 、 C 、 D 四位候选领导人，其中 A 、 B 、 C 三人的思想、观点、作风都不相上下；候选人 D 则观点偏激、做事极端，他故意与前面三个人作对，一心想在竞选中获胜。虽然 A 、 B 、 C 三人大受好评，但他们却处于一个非常不利的地位：由于得票最多的候选人获胜，三人内部的激烈竞争很可能会使他们都输掉竞选。我们假设只有 34% 的人支持候选人 D ，而另外 66% 的候选人都在 A 、 B 、 C 三人之间犹豫不决。最终， A 、 B 、 C 每个人都只得到 22% 左右的票，候选人 D 以绝对的优势获得胜利。但请注意，候选人 D 却是最不受欢迎的那个人。如果按照投票淘汰制进行选举，候选人 D 将在第一轮就被淘汰，因为最不喜欢他的人达到了 66% 。
有人会说，那么干脆以后选举都搞投票淘汰制，每个投票者每轮都选出一位仍未淘汰的人中自己最讨厌的，问题不就解决了吗？这样也有问题——对称地，如果 A 、 B 、 C 三人都很讨厌，投票者会在他们三人之间纠结， D 却反而处于了最不利的地位。因此，要想彻底避免这种问题，我们还得想点儿别的着。
或许有人会对算式 5^2 = 25 有一种特别的偏好——等式左右两边都用到了相同的数字，让人深感奇妙。类似的算式还有很多，例如
5^(6 - 2) = 625
(4 / 2)^10 = 1024
((86 + 2 * 7)^5 - 91) / 3^4 = 123456789
我们自然而然地提出了这样一个问题：这样的算式究竟有多少呢？答案是：无穷多。只需要借助本文一开始提到的算式 5^2 = 25 ，我们就能轻易构造出无穷多个同样满足这种神奇性质的算式来：
50^2 + 0 = 2500
500^2 + 0 + 0 = 250000
5000^2 + 0 + 0 + 0 = 25000000
......
现在，让我们来看看另一类更加精妙的算式：等式两边的数字顺序也完全一样！
- 1 + 2^7 = 127
(3 + 4)^3 = 343
16^3 * (8 - 4) = 16384
这样的算式是否仍然有无穷多个呢？
Mathematica 强大的符号计算和化简能力相信会让不少人震撼不已。输入 Sum[1/n^2, {n, 1, ∞}] ， Mathematica 竟然知道它等于 π^2/6 。我不禁问自己， Mathematica 真的什么都能化简出来吗？今天，我偶然遇到一个简单的表达式， Mathematica 竟然不知道它的精确值。
在 Mathematica 中输入 Cot[π/2] ， Mathematica 会告诉你它等于 0 ；在 Mathematica 中输入 Cot[π/4] ， Mathematica 会告诉你它等于 1 ；但在 Mathematica 中输入 Cot[π/8] ， Mathematica 返回的却还是一个 Cot[π/8] ，并没有给出它的值。而 Cot[π/8] 并不是一个复杂到无法用四则运算和平方开方表达出来的数。在一个边长为 1 的正八边形中，每条边的所对应的“圆心角”为 2π/8 = π/4 ，因此“圆周角” α 就等于 π/8 。由下图我们可以轻易看出， Cot[π/8]=√2+1 。
书架的某一层里放了一套百科全书，但它们排列的顺序却是乱的。一个傻子想要把这套书排好顺序，也就是说他想要书架里的书从左至右分别是第 1 卷，第 2 卷，……，第 n 卷。他给这套书排序的办法是这样的：不断取出一本原应放在更左边的书，插进它该在的位置。比方说，某本书的卷号是 3 ，它的位置却是左起第 5 ，位于其目标位置的右侧。那么傻子就可以把这本书拿出来，插入当前左起第 2 本书的右边，把那些占了它位置的书挤到更右边去，而不管这一操作是否会破坏掉已经就位的书。注意到这种排序法很可能捡了芝麻，丢了西瓜，为了一本书的位置而破坏掉一连串原已排好的书，可谓是鼠目寸光，缺乏远见。我们的问题是，在哪些情况下这样的排序法最终一定能实现排序，哪些情况下可能会陷入永无止境的死循环？
引言 什么是算法
如何寻找稳定的婚姻搭配
据说，一本书开篇就直言不讳地谈起两性的话题，这本书准能畅销。有幸的是，在众多可以用来引入“算法”的话题中，我最喜欢的那一个还真与两性有那么一些关系。假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中的排名(1)，你应该怎样为他们牵线配对呢？
最好的配对方案当然是，每个人的另一半正好都是自己的“第一选择”。这虽然很完美，但绝大多数情况下都不可能实现。比方说，男 1 号的最爱是女 1 号，而女 1 号的最爱不是男 1 号，这两个人的最佳选择就不可能被同时满足。如果出现了好几个男人的最爱都是同一个女孩儿的情况，这几个男人的首选也不会同时得到满足。当这种最为理想的配对方案无法实现时，怎样的配对方案才能令人满意呢？
其实，找的对象太完美不见得是个好事儿，和谐才是婚姻的关键。如果男 1 号和女 1 号各自有各自的对象，但男 1 号觉得，比起自己现在的对象，女 1 号更好一些；女 1 号也发现，在自己心目中，男 1 号的排名比现男友更靠前一些。这样一来，这两人就可能会发生外遇，最后扔下各自现在的对象，一起私奔了——因为这个结果对他们两人都更好一些。在一种男女配对的方案中，如果出现了这种情况，我们就说婚姻搭配是不稳定的。作为一个红娘，你深深地知道，对象介绍得不好没有关系，就怕婚姻关系不稳定。给客户牵线配对时，虽然不能让每个人都得到最合适的，但婚姻搭配必须得是稳定的。换句话说，对于每一个人，在他心目中比他当前的伴侣更好的异性，都不会认为他也是一个更好的选择。现在，我们的问题就是：稳定的婚姻搭配总是存在吗？应该怎样寻找出一个稳定的婚姻搭配？
给大家看一个好玩儿的东西。在不同的显示器上，下面这张图片的显示效果可能大不相同。如果你用的是 TFT 屏幕，上下移动你的脑袋，调整你的视角，你也会看到不同的色彩。从低处往上看，你会看到一个白色的 MM 站在蓝色背景中；从高处往低看，你会看到一个黑色的 MM 站在黄色背景中。
现在，把上面这幅图片保存下来，用你最爱的图象处理软件打开，然后缩放到原图的 50% 。左图是图片缩小后理应得到的结果，但你会发现，你得到的结果是右边的这个图——一片灰色。
Matrix67 |
2010-09-03 7:35 | 
