有問有答有玄機(jī)

揚(yáng)州職業(yè)大學(xué) 林 革

現(xiàn)在有一種名為“20 個(gè)問題”的室內(nèi)游戲，在電視綜藝節(jié)目中屢見不鮮，頗受大眾歡迎。游戲的規(guī)則很簡(jiǎn)單：甲方隨意想到一樣?xùn)|西（可以是人物或物品），乙方則負(fù)責(zé)向甲方提問題，最多只允許提出20個(gè)，問題只能用“是”（對(duì)）或者“不是”（錯(cuò)）回答。乙方要爭(zhēng)取在問答過程中逐步縮小待猜測(cè)事物的范圍，最終準(zhǔn)確判斷甲方所想東西。

舉例如下：甲方是女孩愛麗絲，她選了一個(gè)人，但對(duì)此人的身份保密。乙方是男孩庫茲克，他通過設(shè)計(jì)問題連續(xù)向愛麗絲提問。比如，庫茲克問：“是男人嗎？”“不是。”繼續(xù)提問：“女演員？”“是。”“美國(guó)人？”“不是”……如此繼續(xù)進(jìn)行下去。如果庫茲克能在20 個(gè)問題問完之前猜出愛麗絲選的人，游戲就圓滿結(jié)束。

類似于央視《幸運(yùn)52》中的猜價(jià)格環(huán)節(jié)，要在最短的時(shí)間內(nèi)猜中商品價(jià)格，最為科學(xué)合理的策略就是“中分法”，即不斷取“高了”和“低了”兩個(gè)價(jià)格的平均值，大步快速迫近準(zhǔn)確價(jià)格。而在這個(gè)游戲中最有效率的猜法是，每一個(gè)問題能把剩余的可能性減半。這樣憑借20 個(gè)精心設(shè)計(jì)的問題，就能在百萬人群中找出那個(gè)人。個(gè)中原因仍是“中分折半”，可通過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 萬人連續(xù)減半20 次，就剩下篩選出的那一個(gè)人，這就是提問的最佳方法。

有趣的是，這個(gè)游戲有更多復(fù)雜的變化版本。其中一種是，讓愛麗絲像傳達(dá)神諭的女祭司，偶爾有意無意說些謊話。這時(shí)，數(shù)學(xué)家研究的問題是：愛麗絲可以說謊幾次，使庫茲克問了一定數(shù)量的問題后，仍能猜到正確答案？顯然，在這種情況下可以明確的是：要么庫茲克需要提出的問題超過20 個(gè)，要么選擇的群體人數(shù)較少，才能保證找到那個(gè)神秘的人。那么，在愛麗絲說了幾次謊時(shí)，對(duì)應(yīng)的仍能保證庫茲克猜出正確結(jié)果的群體人數(shù)是多大呢？這就是耐人尋味的“烏拉姆問題”，以波蘭裔美籍?dāng)?shù)學(xué)家斯塔尼斯拉夫·烏拉姆（Stanislaw Ulam）的名字命名。

紐約大學(xué)柯朗數(shù)學(xué)研究所的喬爾·斯賓塞（Joel Spencer），為此花費(fèi)了十多年的時(shí)間進(jìn)行研究。研究結(jié)果表明，解答取決于游戲的精確規(guī)則。在他給出的兩個(gè)版本中：（1）愛麗絲在任何情況下說謊的比例有所限制；（2）允許愛麗絲說謊，但說謊的情形有所限定。比如：在第（1）個(gè)版本中，答題者被允許說謊的比例最多是那么愛麗絲就被允許在8 個(gè)問題中最多說謊8 ×=2（次）；16 個(gè)問題中最多說謊=4（次）等。在第（2）個(gè)版本中，她被允許對(duì)前5 個(gè)問題說謊5 次，但僅此而已，接下來的問題她都必須誠(chéng)實(shí)回答。

對(duì)于這兩個(gè)游戲版本，斯賓塞和一位合作者的研究結(jié)論是：第（1）個(gè)版本中，只有說謊的次數(shù)不超過問題數(shù)的一半，庫茲克才能找出那個(gè)正確的人。如果允許愛麗絲說謊的次數(shù)超過哪怕是一點(diǎn)點(diǎn)，庫茲克就不會(huì)猜中結(jié)果。而第（2）個(gè)版本中，如果允許愛麗絲說謊的比例超過問題總數(shù)的庫茲克也不會(huì)猜中結(jié)果。

以上并非斯賓塞十多年研究的全部。就像樂此不疲的資深玩家一般，他一直致力于這個(gè)游戲的深化和拓展。他與所帶博士生伊萬娜·杜米特留（Ioana Dumitriu）繼續(xù)研究各種條件限制下的游戲情形，難度當(dāng)然也變得越來越大。比如：在一種新設(shè)計(jì)的“半說謊”版本中，愛麗絲只能在真正答案為“不是”時(shí)，才可以說謊；而答案如果為“是”，她必須誠(chéng)實(shí)地作肯定回答。因此不難理解，愛麗絲成為“半說謊者”。

研究結(jié)果表明，即便愛麗絲半說謊，庫茲克仍能以20 個(gè)問題的方式找出正確的人。只不過選擇的群體人數(shù)要比原始版本中的100 萬少得多。具體情況是：如果允許愛麗絲半說謊1 次，群體人數(shù)大幅減少到105000 人；如果允許愛麗絲半說謊2 次，人數(shù)就銳減到22000 人；如果允許愛麗絲半說謊3 次，人數(shù)范圍將要降到7000 以內(nèi)。

如果你認(rèn)為斯賓塞十多年煞費(fèi)苦心，僅僅破解游戲的各種解答有些不值得，那可就大錯(cuò)特錯(cuò)了。比起純粹的游戲樂趣，相關(guān)的研究成果可應(yīng)用于計(jì)算機(jī)信號(hào)傳輸，就顯得非比尋常、尤為重要。因?yàn)橛?jì)算機(jī)信息傳輸?shù)膯挝唬词? 與1 的位串，而20 個(gè)“是”與“不是”的回答，就相當(dāng)于一連串包含0 與1 的位串。如果傳輸線的一端因噪聲而錯(cuò)誤地接收了一些位串，就相當(dāng)于：線路正確傳輸1，但傳輸0 時(shí)不能確定。這就類似于“烏拉姆問題”的半說謊版本。

此外，原始版本的“20 個(gè)問題”游戲是一問一答，庫茲克在問下一個(gè)問題之前就得到反饋，可以針對(duì)前面的答案調(diào)整接下來的問題。斯賓塞和他的博士就此進(jìn)一步擴(kuò)大范疇，設(shè)計(jì)出游戲的另一個(gè)版本：庫茲克必須在游戲開始時(shí)就提出所有問題，并且不知道哪一問愛麗絲會(huì)說謊話。這種更為嚴(yán)格的限制，更符合電信和計(jì)算機(jī)科學(xué)中的現(xiàn)狀：0 與1 通常連續(xù)單向傳輸，不等待響應(yīng)和反饋。針對(duì)于此,計(jì)算機(jī)科學(xué)家利用部分反饋系統(tǒng)抵消這種不利因素：傳輸一定量的位串信息后，送出一個(gè)檢查碼，用以偵測(cè)是否有錯(cuò)。諸如此類不一一贅述。簡(jiǎn)而言之，既然“20 個(gè)問題”游戲和計(jì)算機(jī)信號(hào)傳輸在本質(zhì)上有相通之處，那么相關(guān)研究當(dāng)然能夠應(yīng)用在實(shí)際中，而這正是研究的價(jià)值和意義。