刚刚看到一道智力题，颇有些意思，说来给大家听听。我把题意稍微改了一下，原题中的 XX 侠是一个（不太容易解释的） lynch mob 。
某座城市里发生了一起命案，已经确定凶手是 8 个嫌疑犯之一。经过很多可靠的调查，城南和城北的两名警探各自独立地把嫌疑犯的名单缩减到了两个人。现在，两名警探正在通电话，他们试图对比一下彼此的调查结果。如果他俩的嫌疑犯名单中正好只有一处重合，他们就能确定出凶手的身份了。但问题是，这座城市里有一个伸张正义、凌驾于法律之上的 XX 侠，他正在窃听两名警探的通话。如果他从中获知了凶手的身份，他将在警方实施拘捕之前先杀死凶手。
现在， XX 侠已经知道了那 8 个嫌疑犯是谁，但不知道两名警探各自都把目标锁定在了哪两个人上。这两名警探之前从未见过面，这通电话是他们俩第一次进行交流。他们俩能成功地确定凶手的身份，而又不让 XX 侠知道凶手是谁吗？
（当然，这里我们不允许使用那些基于数论的公钥加密体系，不然题目就没啥意思了）
和大家分享一张超级帅的 T 恤印花，数学各个分支领域中最深刻最神奇的结论在此汇聚一堂，组成了一个心形。
你能从中认出多少个经典的数学研究对象和结论？
经典 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 个人以及他们之前使用“心灵对换机”的记录，至少得引入多少个新的人，才能让所有人的大脑都“物归原主”呢？
目前，我正在《新知客》杂志上主持一个趣题栏目。每月杂志发行后，我将在 Blog 上同步更新。点击 这里 可以查看往期题目。
推理
1. 下一个图形是什么？
2. 小 A 和小 B 玩游戏。小 A 取出一副扑克牌并去掉大小王，剩下红色的牌和黑色的牌各 26 张。洗好牌后，小 A 依次翻开每一张牌，让小 B 看到牌的颜色。小 B 可以在任意时刻打断小 A ，并打赌“下一张牌是红色”。如果下一张牌真是红色，小 A 给小 B 一块钱；如果下一张牌是黑色的，小 B 输给小 A 一块钱。注意，小 B 必须要在某个时刻下赌注，并且机会只有一次；如果他一直没打断小 A ，则默认他赌最后一张牌是红色。
小 B 的最佳策略是什么？在这种策略下，他有多大的概率获胜？
完美的制度是永远不存在。我们可能会产生一种觉得某某制度很完美的错觉，这只是因为我们习惯了它而已。若把这个制度拿出来仔细琢磨琢磨，你会发现它还存在太多的问题。
我们习惯了“多数票当选”的选举制度。每个投票者把自己手中的票投给其中一位候选人，得票数最多的候选人即获胜，因为他的支持者最多。这看上去似乎挺合理。但在实际生活中，这种选举制度并不见得总是合理的——得票数最多的候选人很可能并不是大家喜欢的候选人。有时候，获胜的候选人竟会是最不受欢迎的那个人。
假设有 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 却反而处于了最不利的地位。因此，要想彻底避免这种问题，我们还得想点儿别的着。
昨天的消息：一位 HP 的研究员 Vinay Deolalikar 宣称自己证明了 NP 问题，得出了 P≠NP 的结论。 P 是否等于 NP ，这是计算机科学领域中最困难的问题之一，也是意义最深远的问题之一，长期以来一直备受争议。如果这个问题获得解决，将会在各个科学领域中引起轰动。 Vinay Deolalikar 的整个证明有 100 多页，详细的论文可以在这里看到：
http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
Stanford 的博士后 randomwalker 看完证明后表示，很多迹象表明，这个证明很有可能是正确的。
－－－－－－－－－－－－－－－－－－－－－－－－－－－
今天早晨的消息： Morley Davidson 、 John Dethridge 、 Herbert Kociemba 和 Tomas Rokicki 宣称，他们已经利用计算机，完美地解决了魔方问题。他们验证了，任何一种魔方的初始状态都可以在 20 步以内解出。他们将 43,252,003,274,489,856,000 种初始状态分为了 2,217,093,120 组，再利用对称性和集合覆盖将规模缩小到了 55,882,296 组。他们的程序可以在 20 秒左右求解出一组问题的解法，最终利用 Google 提供的强大的计算机，彻底解决了魔方问题。
利用组合数学，我们能够证明，存在一种魔方初始状态，它需要至少 18 步才能解决。 1995 年， Michael Reid 找到了一种最少需要 20 步才能获解的魔方初始状态，因而将魔方问题的下界提高到了 20 。此后，数学家们猜想，任意给定一个魔方的初始状态，最多 20 步就能解决。 2008 年， Tomas Rokicki 和 John Welborn 证明了，任意一个魔方初始状态都可以在 22 步以内解决。 2010 年 7 月，这个上界终于降低到了 20 ，从而完成了对魔方最优解问题数十年来的探索。
详细的研究成果见这里：
Matrix67 |
2010-09-03 7:35 | 
