有問有答有玄機

揚州職業(yè)大學 林 革

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

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

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

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

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

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

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

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

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

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