IBM Ponder This上个月的题目比较有趣：我在心里面想一个2到166之间的整数（包括2和166），你的任务是用尽可能少的是非问句（我只能回答是或者否）猜出这个数除1以外的最小约数是多少。
(1) 寻找一种策略使得在最坏情况下猜到答案的询问次数最少。
(2) 寻找一种策略使得在平均情况下猜到答案的期望询问次数最少。
第一个问题很容易回答。虽然2到166之间的整数一共有165个，但它们的最小约数（以后我们说的“最小约数”都是指的不包括1的最小约数）只有38种。因此，事实上你只需要用二分法在38个可能的答案当中找出一个就可以了。由于2^5=32，2^6=64，因此最坏情况下需要6次询问才能保证猜到。
真正困难的是后面一个问题：要想让平均猜测次数尽可能少，我们该从哪里入手呢？
前几天有网友推荐我看一部日剧叫做《欺诈游戏》，据说里面的高智商较量非常强大。最近这几天我看了前面几集，感觉和之前看过的一些推理日剧一样——剧情相当精彩，可惜拍得很烂。或许是不习惯日剧本身的画面风格吧。从第三集起，剧集进入了欺诈游戏第二场比赛之少数决游戏，有一段剧情相当科学。
欺诈游戏的第二场共有22人参加。这22个人集中在一个阴森的大厅里，参加一个叫做“少数决”的游戏。游戏规则很有意思：主办方随机抽取一个人到台上来，向众人问一个二选一的问题，比如“你信春哥吗”。每个人手里都会得到两张选票，两张选票上都印有自己的名字，但其中一张纸上印有“YES”，另一张纸上印有“NO”。游戏者们有6个小时的时间进行交流和考虑，并要在时间结束前将自己的选择投入投票箱。时间结束后，主办方进行唱票，并规定票数较少的那一方取胜，多数派将全部被淘汰。获胜的选手将进行新一轮的游戏，主办方从剩下的人中重新选一位进行提问，并要求大家在6个小时内投票，唱票后仍然宣布少数派胜出。若某次投票后双方人数相等，则该轮游戏无效，继续下一轮。游戏一直进行下去，直到最后只剩下一人或两人为止（只剩两人时显然已无法分辨胜负）。所有被淘汰的人都必须缴纳罚金，这些罚金将作为奖金分给获胜者。
这个游戏有很多科学的地方，其中最有趣的地方就是，简单的结盟策略将变得彻底无效。如果游戏是多数人获胜，那你只要能成功说服其中11个人和你一起组队（并承诺最后将平分奖金），你们12个人便可以保证获胜。但在这里，票数少的那一方才算获胜，这个办法显然就不行了。因此，欺诈和诡辩将成为这个游戏中的最终手段。如果你是这22个参赛者中的其中一个，你会怎么做呢？
在计算机复杂度理论中，P问题指的是能够在多项式的时间里得到解决的问题，NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看，如果哪一天科学家证明了P=NP，寻找一个解和验证一个解变得同样容易，那这个世界将会变得怎样？
已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。
算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。
一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的编程语言中，你只需要用代码指明输入数据与输出数据的关系，而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的，编译器将自动找到解法。在新型编程语言的支持下，人们唯一需要考虑的是，如何把实际问题转化成数学模型。
在各种介绍密码学与协议的教材里都有关于零知识证明的话题——如何让你相信我已经找到了一个解，但又不告诉你这个解是什么。最经典的例子便是关于Hamilton回路的问题——存在这样一种巧妙的协议，可以让你相信我已经找到了某个图的Hamilton回路，而你却完全得不到关于这个Hamilton回路本身的任何信息。今天我又看到了一个非常不错的零知识证明实例。给定一个平面图，你需要给每个区域染一种颜色，使得任两个相邻的区域颜色不同。如果你仅用三种颜色就能做到这一点，我们就说这个图是可以三染色的。目前我们还没有一个判断平面图可否三染色的好办法，寻找一个平面图的三染色方案并不是一件容易的事。现在，假如你已经找到了某个给定平面图的三染色方案，你想向别人炫耀自己的成果，但又不想透露关于你的染色方案的任何信息。你能否设计一种协议使得对方能够相信你确实找到了一种三染色方案而又不告诉他这种方案是什么呢？
今天下午在上语言统计分析课时，我听到了一个非常有趣的问题。考虑同时抛掷两个骰子所得到的结果——它们的和有1/36的概率得到2，有2/36的概率得到3，……，有1/36的概率得到12。现在，你能否构造两个新的骰子，使得同时抛掷两个新骰子的结果与原来相同？注意，每个骰子都有6个面，每个面都有一个正整数。这些点数可能超过6，并且可能会有重复。另外，这两个骰子也无需完全相同。
解决这个问题并不难。首先注意到，为了使得两个骰子的点数之和能够得达到2，每个骰子上都得有一个“1”（并且仅有一个“1”）才行。接下来考虑，为了得到两种和为3点的情况，我们还得在两个骰子上放置两个“2”：我们可以在每个骰子上各放一个“2”，不过这样就与原来的骰子没啥区别了；我们也可以来点不一样的，把两个“2”都放在一个骰子上。现在，其中一个骰子上只放了一个“1”，另外一个骰子已经填了一个“1”和两个“2”，这可以保证它们能产生出一个2点和两个3点。再下一步，我们将考虑如何产生出三个4点。为此，我们需要把三个“3”分配到两个骰子中。这样推下去虽然越来越麻烦，但最终你还是能得到一个合法解：一个骰子上写有1、2、2、3、3、4，另一个骰子上写有1、3、4、5、6、8。不过，这个问题有一个异常巧妙的解法，它能够把两个骰子的点数进行整体求解。你能想到这个做法吗？