很久没有更新和信息学有关的东西了。今天和大家分享一个非常有趣的题目，我已经很久没看见如此精彩有趣的题目了。为了引入这个问题，我们先来介绍一个假想的编程语言QCPL。就像LISP一样，它是一个基于函数的语言：没有变量，没有for循环，一切东西都是用函数来表示的。另外，就像FORTRAN一样，QCPL语言不支持递归，也就是说一个函数不能递归地调用自己。QCPL的另一个有趣的特点是，所有的函数都只能返回一个Boolean值。比如说，下面这个函数的作用就是判断x+2和y+2的乘积是否等于z：
MULT_PLUS_TWO(x,y,z): (x+2)*(y+2)=z

    QCPL也有逻辑运算符。事实上，QCPL里的合法运算符一共只有8个，其中6个分别如下：

运算符 |  作用  |     输入      |     输出
——-+——–+—————+—————
  +    |  相加  |  两个自然数   |  一个自然数
  *    |  相乘  |  两个自然数   |  一个自然数
  =    |  等于  |  两个自然数   | 一个Boolean值
  &    | 逻辑和 | 两个Boolean值 | 一个Boolean值
  |    | 逻辑或 | 两个Boolean值 | 一个Boolean值
  !    | 逻辑非 | 一个Boolean值 | 一个Boolean值

    另外两个运算符就要重点介绍了。这是QCPL语言真正牛B的地方——它是专门为量子计算机设计的！你可以让这台计算机平行地穷尽完某些变量所有可能的取值，这一切仅仅在一瞬间内就可以完成。这两个特殊的运算符（以后我们管它们叫做“定量运算符”）就是专门用来干这件牛B事的："Ex"是“存在性定量运算符”，表示让计算机找出是否存在一个满足表达式的自然数x；"Ax"是“通用性定量运算符”，用于询问计算机该表达式是否对所有的自然数x均成立。比如，运用定量运算符，我们可以立即写出素数/合数判断函数：
COMPOSITE(n): Ex,Ey,MULT_PLUS_TWO(x,y,n)
PRIME(n): !(COMPOSITE(n)|n=0|n=1)
    其中，Ex,Ey,MULT_PLUS_TWO(x,y,n)的意思就是说，是否存在某一对x和y，使得MULT_PLUS_TWO(x,y,n)为真。只要（某一个平行世界里的）计算机找到了任何一对满足条件的x和y，整个COMPOSITE(n)立即返回True。如果对于所有的自然数x和y，MULT_PLUS_TWO(x,y,n)都不可能为真时，整个函数才返回False。别忘了这是一台量子计算机，穷举的过程可以在一瞬间内完成。

    好了，下面我们再给出几个基本的函数。函数SUM用于计算x加y是否等于z，而函数PRODUCT则用于检验x乘以y是否等于z：
SUM(x,y,z): x+y=z
PRODUCT(x,y,z): x*y=z
    现在，你的任务就是写出一个函数POWER(x,y,z)，当且仅当x的y次方等于z时函数才返回True。相信我，这道题没有那么容易。
Read more…

    三个人坐成一个圆圈，每个人头上戴着一顶黑色的或者白色的帽子。每个人都只能看到另外两个人头上的帽子颜色。现在，他们需要独立地猜测自己头上的帽子颜色。每个人都需要在自己的小纸条上写下“黑色”、“白色”或者“放弃”。如果说至少一个人猜对，并且没有人猜错，那他们就获胜了；只要有任何一个人猜错，或者所有人都写的“放弃”，那么他们就输了。如果在游戏开始前他们能够商量一个策略，那么最好的策略是什么？
    仔细想一下你会发现，要想保证他们百分之百地获胜是不可能的，因为游戏中大家不能交流信息，谁也不能保证自己能猜对。但是，有一种策略能保证他们有75%的几率获胜。事实上，当人数n=2^k-1时，我们有一种方法可以让获胜的概率达到(2^k-1)/(2^k)。你能想到这种策略吗？

    设身处地地想，你会想到一个很自然的策略：如果一个人看到另外两个人的帽子颜色一黑一白，那这个人就放弃（换了你你也不敢猜）；如果另外两个人的帽子颜色一样，那你就猜相反的颜色（概率上看也要大些）。我们来看一下在哪些情况下使用这样的策略能够获胜：

3个黑帽子：每个人都看到两个黑帽子，每个人都猜自己是白帽子，所有人都猜错；
2个黑帽子，1个白帽子：戴黑帽子的人看到一黑一白，于是放弃；戴白帽子的人看的是两个黑帽子，因此他将猜对，从而所有人都获胜；
2个白帽子，1个黑帽子：和上面这种情况是类似的，所有人都将获胜；
3个白帽子：和第一种情况是类似的，所有人都猜错。

    注意到只有在第一种情况和第四种情况下才会输掉游戏，这两种情况占了所有情况的2/8。于是，使用这种策略有75%的概率获胜。

    我们需要想一想，在这个看似几乎不可能获胜的游戏中，为什么这种策略会有如此高的获胜概率。最关键的就是，这种策略充分利用了胜负判断的准则：大家要错就一起错，只有一个人错怪划不来的；要获胜就只让一个人猜对，多几个人同时猜对也没用。

    根据上面的讨论，我们开始尝试把游戏的人数推广到一般的n。为了叙述方便，我们把每个人头顶上的帽子颜色依次用0和1来表示，数字1表示黑帽子，数字0表示白帽子。于是所有可能的情况就是2^n个01串。游戏开始前n个人预先约定一些“保留串”。他们的策略就是，观察其余n-1个人的帽子颜色：如果和所有的保留串都不匹配里，则放弃；如果恰好符合某个保留串，就猜自己是相反的颜色。比如，当n=3时，他们可以约定两个保留串000和111。如果实际情况是001的话，前两个人看到的是?01和0?1，不属于任何一个保留串，于是放弃；第三个人看到的是00?，正好和000相符，于是他就反过来猜自己不是那个0。注意到一些有趣的事实：如果实际情况恰好就是这些保留串之一，那大家就全猜错了；如果实际情况与所有保留串都相差两个数字以上，那大家全部放弃；如果实际情况与某个保留串恰好差一个数字，那只有一个人猜对，其余人放弃，从而获得胜利。现在的问题就是，如何寻找一个保留串集合，使得和某个保留串只差一个数字的情况尽可能的多。注意，我们必须要保证，任意两个保留串之间不能只差一个数字，这样的话才能保证发现有相符保留串的人不会面临“两可”的情况。假如你找到了t个保留串，则保证获胜的情况最多有t*n个（每个串“变一位”都有n种方法）。显然，最完美的情况就是t+t*n恰好等于总的情况数2^n。当n=2^k-1时，t+t*n是有可能恰好等于总情况数2^n的，也就是说每种可能的情况要么就是一个保留串，要么与唯一的一个保留串恰好差一位。此时，t+t*n=t(n+1)=t*(2^k)=2^(2^k-1)，t应该等于2^(2^k-1-k)。下面我们说明这t个保留串是如何生成的。
    每个保留串都由原码和校验码两部分组成。我们把n位01串的位置编号转化为二进制，二进制里只有一个数字1的位置（即左起第1,2,4,8,…位）叫做校验码，有至少两个1的位置（3,5,6,7,9,…等其余位置）上的数字称作原码。显然，原码应该有n-k位（即2^k-1-k位）。枚举2^(n-k)种原码的01组合，对于每一组原码，定义第i个校验码的值为，除了它本身以外，所有编号的二进制表达中右起第i个数字为“1”的位置上一共有奇数个1还是偶数个1（相当于把标“x”的位置上的数异或一遍）。比如，第2个校验码是1，当且仅当有奇数个位置上的原码满足，位置编号的二进制表达形如…???1?且该位置上的数值正好也是1。所有可能的原码加上它对应校验码就是我们的保留串。

  01串:     a1  a2  a3  a4  a5  a6  a7
十进制编号:  1   2   3   4   5   6   7

二进制编号: 001 010 011 100 101 110 111
校验码1(a1):         x       x       x
校验码2(a2):         x           x   x
校验码3(a4):                 x   x   x
保留串0:     0   0   0   0   0   0   0
保留串1:     1   1   0   1   0   0   1
保留串2:     0   1   0   1   0   1   0
保留串3:     1   0   0   0   0   1   1
保留串4:     1   0   0   1   1   0   0
   ……      ……     ……        
保留串14:    0   0   1   0   1   1   0
保留串15:    1   1   1   1   1   1   1

    我们可以说明，对于任一个n位01串，只要它不是我们的保留串，我都有办法只变动一个数字让原码和校验码相符（从而变成一个保留串）。我们可以观察一下，由原码算出来的校验码和实际的校验码有哪些不同。如果只有一位校验码不同，直接把它改过来就是了；如果有多位校验码不同，那就找出改动哪一位原码可以让这些校验码同时取反。从位置编号的二进制的角度来考虑，这样的一位原码显然是唯一存在的。同时，我们可以保证任两个

    今后决定把较长的文章分段发布，不然大家读着太累。况且篇幅短一些的话，RSS输出也好看些:)

    在讲问题的加强版之前，让我们先来回忆一下经典的100囚犯问题（不是灯泡）。
    100个囚犯从前往后坐成一列。坐在最后面的那个囚犯能够看到其余99个囚犯，坐在最前面的那个囚犯啥也看不见。看守给每个囚犯戴上一顶黑色的或者白色的帽子。然后，看守会从后往前依次叫这些囚犯猜测自己头顶上的帽子的颜色。如果哪个囚犯猜对了，他就自由了。坐在前面的每一个囚犯都可以听到后面的囚犯的猜测。如果这100个囚犯事先可以商量好一种策略，那么最理想的策略是什么？
    囚犯们可以乱猜一通，最坏情况下所有人都猜错，平均下来则会有50个人猜对。这个题有趣的地方就在于，100个囚犯事先可以商量一种策略，也就是说坐在后面的囚犯可以用他的猜测给坐在前面的囚犯透露一些信息。很显然，坐在最后面的囚犯是不可能保证自己猜对的，他猜黑猜白都只有一半的几率猜对，似乎没什么区别；但囚犯可以事先约定好一种暗号，即最后一个囚犯猜黑表示什么意思，猜白表示什么意思。比如，最后一个囚犯可以猜测和他前面的囚犯的帽子一样的颜色，这就相当于用他的猜测告诉了他前面那个囚犯该猜什么，于是坐倒数第二的囚犯可以保证被释放；此时，坐在倒数第三个位置上的囚犯面对与刚才坐最后的囚犯相同的处境，他同样可以用他的猜测提示出他前面那个人的帽子颜色。这样下去，可以保证至少50个人猜对，平均情况则有75个人猜对。这不是最佳的策略。
    不可思议的是，最佳策略可以保证，除了坐在最后面的囚犯以外，其余99个囚犯都能猜对。你能想出这样的策略是什么吗？继续看下去前不妨先想一下。

    前面那种策略的问题在于，坐在最后面的那个人透露出的信息不多。他完全可以透露出与全局相关的一些信息，因此以后所有的人都可以用这条信息。比如，他可以数一数他前面99个人一共有多少顶白帽子，并约定他猜“黑”表示他前面共有偶数顶白帽，他猜“白”表示他前面共有奇数顶白帽。坐倒数第二的那个人也数一数他前面98个人的白帽子个数：如果他数出来的个数与先前透露出的个数一奇一偶，则他自己肯定戴的是白帽子；如果他数出来的和先前透露的结果奇偶性相同，则他自己戴的肯定是黑帽子。这样，坐倒数第二的保证可以猜对了。那接下来咋办呢？不要忘了，其他囚犯能听到刚才那人猜的是什么，并且知道他的猜测保证是对的。这相当于每个人不仅能看到坐他前面的所有人的帽子颜色，还知道他背后那些人的帽子颜色，结合最初的那个奇偶性信息，接下来的每一个人都可以猜出自己脑袋上的帽子颜色。这样下去，至少99个囚犯可以保证被释放。这种策略显然是最佳的，不可能再有什么策略能保证所有人都被释放，因为至少坐最后的那个人不可能保证自己猜对。

    真正有趣的东西来了。下面提出这个问题的加强版，囚犯的数目加强到无穷个！你将看到“无穷”这个神秘的东西再一次开始作怪。

最后报怨一句：刚才不小心看到莲蓬乳了

    今天在回访网站流量来源时看到了一个很牛B的东西，和大家分享一下。
    给定一个顶点数为100000的图G，问是否存在Hamilton回路。现在，A宣称自己已经找到了一个Hamilton回路，但B不信，要A证明给他看。你能否想出一个办法使得，A可以让B相信自己有了正确的答案，但B依然不知道答案是什么。这种方法既科学又有趣，整个过程不需要第三者参与，仅仅靠AB两人之间的交流即可。这种方法可以让B有充分的理由相信A找到了Hamilton回路，但能保证B仍然得不到任何与正确答案有关的线索。

    首先，A生成一个100000的全排列P，然后用这个排列P把原图G的顶点标号打乱（对标号进行置换），这样就得到了一个同构的图G'。然后A把图G'告诉给B。注意，目前判断两个图是否同构还没有有效的P算法，因此除非A把排列P也告诉了B，否则B不知道G'和G是不是真的同构。接下来B从下面这两个问题中随机抽一个问题让A作答：叫A证明G与G'同构（即叫A给出排列P，确保他没有作假），或者叫A指出G'中的一条Hamilton回路。反复进行“构造G'—抽问”的过程，每次A答对后B都会更加确信A确实找到了原图G的Hamilton回路，来个十几二十次后A作假的嫌疑基本上可以被排除了。这是因为，如果A不知道原图G中的Hamilton回路，这两个问题他是不可能同时答对的，既然B是抽查的，A不可能每次总能答对。同时，除非B同时知道了两个问题的答案，否则B永远不知道原图G的Hamilton回路是什么。仅仅知道G'的Hamilton回路是没有用的，因为此时B连G和G'是否同构都不知道，更别提找出它们之间的对应关系了。

来源：http://www.zju88.cn/cgi-bin/bbstcon?board=Algorithm&file=M.1200769543

    SETI@home可以在杂乱的射电数据中搜寻独特的讯号，你能在大街上的嘈杂声中清晰分辨出一个尖细的女声大叫“亚美蝶”。这些现象都表明，有时对集合里的所有元素进行整体考察可以很快找出我们所要找的个体。去年我们搞合唱比赛时，我又想到了一个绝佳的例子：你可以在合唱声中清楚地听到是否有人跑调。考虑这样一个问题，假如合唱团里有一个人唱歌始终走调，但我听不出来是谁走调，只能听出当前正在唱歌的人中是否有唱走调了的人。那么，我如何才能迅速地揪出那个唱走调的人？利用经典二分法，我们可以在log2(n)次合唱后找出唱走调了的人。每一次，我都把剩下的人平均分成两组，然后选其中一组来合唱：如果听不到走调的声音，这一组的人就全部过关；如果听到有人走调，那另一组里的人都可以被排除了。递归地对剩下的组进行同样的操作，log2(n)次操作后必定可以找出那个唱歌走调的人。
    现在的问题变得有些麻烦了。假如我们知道合唱队里有一个人唱歌爱跑调，但他不是总会跑调。具体地说，他只有1/2的概率唱错，但其余1/2的时间里他却唱得很准。现在，传统的二分法不再适用了，因为没有走调声已经不能起到排除的作用了。你能想出多少种可行的算法来找出那个人？下面提出一些可行的方法，你认为哪种方法更好？你能求出这些算法所需要的检测次数的期望值各是多少吗？

    1. 不断地随机生成一个大小为n/2的子集并对其进行检测，直到某次不能通过检测为止，然后递归地对其进行操作。
    2. 所选的子集大小为n/2是最优的吗？把上面这种方法的n/2改成n/a，常数a的最优值是多少？
    3. 检测次数的期望值还可以更小吗？我们想到，每次都重新生成一个新的集合其实并不科学，新集合本身是否包含老鼠屎也是得碰碰运气的。因此，对方法1的一个合理改进是：把集合平均划分为两个部分，交替对它们进行检测直到某次检测没通过为止，然后对该组递归操作下去。这种方法真的比前两种好吗？它所需要的期望次数是多少？
    4. 尝试对方法3进行改进。如果把集合平均划分成3份并循环进行检测，效果会不会更好一些？

    1. 选取的子集有1/2的概率覆盖了我们要找的那个人，子集里有他而他这次恰好又唱走调了则有1/4的概率。因此，不管规模有多大，平均需要4次才能把规模缩小一半。因此，检测次数的期望值为4*log2(n)。为了方便比较期望值的大小，后面的答案我们一律表示成一个常数乘以log2(n)的形式。
    2. 类似地，平均需要2a次检测才能把规模缩小到原来的1/a，因此总共花费的检测次数为2a*log2(n)/log2(a)。对函数求导，可得当a为e时函数值达到最小。此时的检测次数期望值为2e*log2(n)/log2(e)≈3.7683 * log2(n)。
    3. 这个就经典了。设方法3里把规模缩小一半所需要的检测的期望次数为m，下面我们来看m应该等于多少。把n个人平均分成两组，我们要找的老鼠屎有1/2的概率在第一组，有1/2的概率在第二组。因此，第一次就测出问题来有1/4的可能，第二次就测出问题也有1/4的可能。对于剩下的1/2种情况，局面变得又和最开始一样，只是平均需要的检测次数比原来多了2。根据期望值的定义，有m=(1/4)*1 + (1/4)*2 + (1/2)*(m+2)，解得m=3.5。总的检测次数就是3.5 * log2(n)，它比前面两种方法都要好。你可能不同意上面求m的方法。这没啥，如果你不断对m进行迭代，你会发现展开出来的式子就是最标准的期望值定义。
    4. 类似地，有m=(1/6)*1 + (1/6)*2 + (1/6)*3 + (1/2)*(m+3)，解得m=5。于是，把规模缩小到原来的1/3平均需要5次检测，总的检测次数为5*log2(n)/log2(3)≈3.1546 * log2(n)。

题目来源：IBM Ponder This Dec07
原文还从熵的角度探寻了问题的最优算法，感兴趣的读者可以去看一看