有问有答有玄机

扬州职业大学 林 革

现在有一种名为“20 个问题”的室内游戏，在电视综艺节目中屡见不鲜，颇受大众欢迎。游戏的规则很简单：甲方随意想到一样东西（可以是人物或物品），乙方则负责向甲方提问题，最多只允许提出20个，问题只能用“是”（对）或者“不是”（错）回答。乙方要争取在问答过程中逐步缩小待猜测事物的范围，最终准确判断甲方所想东西。

举例如下：甲方是女孩爱丽丝，她选了一个人，但对此人的身份保密。乙方是男孩库兹克，他通过设计问题连续向爱丽丝提问。比如，库兹克问：“是男人吗？”“不是。”继续提问：“女演员？”“是。”“美国人？”“不是”……如此继续进行下去。如果库兹克能在20 个问题问完之前猜出爱丽丝选的人，游戏就圆满结束。

类似于央视《幸运52》中的猜价格环节，要在最短的时间内猜中商品价格，最为科学合理的策略就是“中分法”，即不断取“高了”和“低了”两个价格的平均值，大步快速迫近准确价格。而在这个游戏中最有效率的猜法是，每一个问题能把剩余的可能性减半。这样凭借20 个精心设计的问题，就能在百万人群中找出那个人。个中原因仍是“中分折半”，可通过220=（210）2=1 0242≈1 0002=1 000 000=100 万→219→218→217→216→215→214→213→212→211→210→……→23→22→21→20=1 直观示意。也就是说，100 万人连续减半20 次，就剩下筛选出的那一个人，这就是提问的最佳方法。

有趣的是，这个游戏有更多复杂的变化版本。其中一种是，让爱丽丝像传达神谕的女祭司，偶尔有意无意说些谎话。这时，数学家研究的问题是：爱丽丝可以说谎几次，使库兹克问了一定数量的问题后，仍能猜到正确答案？显然，在这种情况下可以明确的是：要么库兹克需要提出的问题超过20 个，要么选择的群体人数较少，才能保证找到那个神秘的人。那么，在爱丽丝说了几次谎时，对应的仍能保证库兹克猜出正确结果的群体人数是多大呢？这就是耐人寻味的“乌拉姆问题”，以波兰裔美籍数学家斯塔尼斯拉夫·乌拉姆（Stanislaw Ulam）的名字命名。

纽约大学柯朗数学研究所的乔尔·斯宾塞（Joel Spencer），为此花费了十多年的时间进行研究。研究结果表明，解答取决于游戏的精确规则。在他给出的两个版本中：（1）爱丽丝在任何情况下说谎的比例有所限制；（2）允许爱丽丝说谎，但说谎的情形有所限定。比如：在第（1）个版本中，答题者被允许说谎的比例最多是那么爱丽丝就被允许在8 个问题中最多说谎8 ×=2（次）；16 个问题中最多说谎=4（次）等。在第（2）个版本中，她被允许对前5 个问题说谎5 次，但仅此而已，接下来的问题她都必须诚实回答。

对于这两个游戏版本，斯宾塞和一位合作者的研究结论是：第（1）个版本中，只有说谎的次数不超过问题数的一半，库兹克才能找出那个正确的人。如果允许爱丽丝说谎的次数超过哪怕是一点点，库兹克就不会猜中结果。而第（2）个版本中，如果允许爱丽丝说谎的比例超过问题总数的库兹克也不会猜中结果。

以上并非斯宾塞十多年研究的全部。就像乐此不疲的资深玩家一般，他一直致力于这个游戏的深化和拓展。他与所带博士生伊万娜·杜米特留（Ioana Dumitriu）继续研究各种条件限制下的游戏情形，难度当然也变得越来越大。比如：在一种新设计的“半说谎”版本中，爱丽丝只能在真正答案为“不是”时，才可以说谎；而答案如果为“是”，她必须诚实地作肯定回答。因此不难理解，爱丽丝成为“半说谎者”。

研究结果表明，即便爱丽丝半说谎，库兹克仍能以20 个问题的方式找出正确的人。只不过选择的群体人数要比原始版本中的100 万少得多。具体情况是：如果允许爱丽丝半说谎1 次，群体人数大幅减少到105000 人；如果允许爱丽丝半说谎2 次，人数就锐减到22000 人；如果允许爱丽丝半说谎3 次，人数范围将要降到7000 以内。

如果你认为斯宾塞十多年煞费苦心，仅仅破解游戏的各种解答有些不值得，那可就大错特错了。比起纯粹的游戏乐趣，相关的研究成果可应用于计算机信号传输，就显得非比寻常、尤为重要。因为计算机信息传输的单位，即是0 与1 的位串，而20 个“是”与“不是”的回答，就相当于一连串包含0 与1 的位串。如果传输线的一端因噪声而错误地接收了一些位串，就相当于：线路正确传输1，但传输0 时不能确定。这就类似于“乌拉姆问题”的半说谎版本。

此外，原始版本的“20 个问题”游戏是一问一答，库兹克在问下一个问题之前就得到反馈，可以针对前面的答案调整接下来的问题。斯宾塞和他的博士就此进一步扩大范畴，设计出游戏的另一个版本：库兹克必须在游戏开始时就提出所有问题，并且不知道哪一问爱丽丝会说谎话。这种更为严格的限制，更符合电信和计算机科学中的现状：0 与1 通常连续单向传输，不等待响应和反馈。针对于此,计算机科学家利用部分反馈系统抵消这种不利因素：传输一定量的位串信息后，送出一个检查码，用以侦测是否有错。诸如此类不一一赘述。简而言之，既然“20 个问题”游戏和计算机信号传输在本质上有相通之处，那么相关研究当然能够应用在实际中，而这正是研究的价值和意义。