Sroan指着一块手表的表面对Pasber说:“请你在表面上表示小时的12个数字中默认一个数字。现在我手中有一枝铅笔。当我的铅笔指着表面上的一个数字时,你就在心里默念一个数。我将用铅笔指点表面上的一系列不同的数,你跟随我在心里默念一系列数。注意,你必须从比你默认的数字大1的那个数字开始默念,例如,如果你默认的数字是5,你就从6 开始念,然后按自然数顺序朝下念,我指表面上的数,你默念心里的数,我显然不知道你心里默念的是什么数,当你念到20 时,就喊‘停’,这时我手中的铅笔,一定正指着你最初默认的数。” Pasber认为这是不可能的,因为Sroan并不知道自己从哪个数字开始默念。但出乎意料的是,当他按Sroan所说的操作一遍后,Sroan手中的铅笔正指着他心里默认的那个数字!
想想看,Sroan是如何做到这一点的?
考虑一个传统的猜数游戏。 A 、 B 两名玩家事先约定一个正整数 N ,然后 A 在心里想一个不超过 N 的正整数 x , B 则需要通过向 A 提问来猜出 A 心里想的数。 B 的问题只有唯一的格式:先列出一些数,然后问 A “x 是否在这些数里”, A 则需要如实回答“是”或者“否”。显然, B 是保证能猜到 x 的,只需要依次询问“x 是否等于 1 ”,“x 是否等于 2 ”即可。由于 B 可以精心选出满足某种特征的所有数,询问 x 是否在这些数里,因而 B 还可以做得更好。例如当 N = 16 时, B 第一次可以问“x 是否小于等于 8 ”,或者等价地,“x 是否属于 {1, 2, 3, 4, 5, 6, 7, 8} ”;接下来,根据 A 的回复继续细问“x 是否小于等于 4 ”或者“x 是否小于等于 12 ”,以此类推。另一种方法则是询问“x 的二进制表达的第一位是否是 1”,“x 的二进制表达的第二位是否是 1”,以此类推,从而获得 x 的二进制表达的所有数位,便能推出 x 来。
现在,有意思的问题来了。假设 A 可以偶尔说谎(但保证不会连续说谎两次),那么 B 还能通过询问猜出 A 所想的数吗?如果愿意的话, B 可以询问任意多次。