说下第二十九题。
第二十九题看似比第二十七题难得多,但第二十九题中存在一个十分强大的共有信息——日期!这让第二十九题的编码变得非常简单。
下面商定一个编码。
把所有的正整数按如下方式排成一列:
1 1-2 1-2-3 1-2-3-4.....
记作数列A。这个数列的特点是: 任何正整数都在此数列中出现了无数次。 (很重要!)
接下来把A中的所有数进行二进制化,然后直接排在一起:
1 1-10 1-10-11 ......
就形成了一个二进制序列,不妨记作P。
下面定义三个动作“发送”,“接受”和“沉默”:
发送一个自然数x: 当且仅当{当前日期n对应的数列P的第n位恰好是数列A中值为x的某一项的某一位,且正好潘多拉来要球}时,给他一个对应P[n]的球(黑0,白1); 其他时候潘多拉要球,全给黑球。
接受一个自然数x:如果{在数列A中值为x的某一项所对应的数列P中的所有位所对应的日期n中} 均收到了{数列P中对应的值P[n]}, 则记作收到了自然数x。
沉默:只给黑球。
容易证明以下结论:
1 如果某人一直发送x,则对其他任何人,总有一天能收到x。
2 如果某人收到了x, 则一定有其他人正在发送x。
这两个强大的结论使得囚犯们之间的交流极其顺畅。毕竟所有现代汉语所能构成的文本数量也是可数的,因此,通过把“所有现代汉语文本”与自然数一一对应,囚犯们可以直接用现代汉语交流。设想如下场景:每个人对着天空大喊,他们不知道自己的喊声会不会被听到,但只要一直喊下去,总有一天所有人都会听到。
如果数字没有重复,问题到这里已经解决了:每个囚犯只要大喊自己的数字即可。于是在信道P上同时存在着大量的信息:“我是2!” “我是3!” “我是1.414!”...蓝蘑菇每听到一个数字,就往纸上加一个数字;而总有一天,蓝蘑菇会听到所有人的数字。
但现在数字有重复。怎么办呢?
也很简单:每个人把潘多拉第一次向自己要球的日期记作自己的ID,每次大喊时喊出自己的ID即可。显然每个人的ID都是不同的;当蓝蘑菇听到同样的数字来自不同的ID时,他就可以写下这些重复的数字了。