克洛伊剛從她的長曲棍球比賽回來，她的雙胞胎弟弟泰勒就打來了電話。“亨利警官想過來。看來他要處理一些不可靠的目擊證人，” 泰勒在她接起電話後告訴她。
亨利警官對於這兩個十二歲的孩子來說是一個熟悉的人物，他已經開始依賴他們幫助處理棘手的案件。他自己也是一個聰明且認真的謎題研究者，他通常以給雙胞胎們上一堂簡短的歷史課來開始他的案情介紹。
“在許多經典的謎題中，人們要麼總是說真話，要麼總是說謊，” 他開始說。“你問他們問題，要麼你確定誰是說謊者，要麼你在不明確確定任何人的誠實度的情況下發現一些事實。”
支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道： 訂閱。 透過購買訂閱，您正在幫助確保有關塑造我們今天世界的發現和想法的有影響力的故事的未來。
“例如，這是我認為經典的謊言問題中的女王。 你在一個陌生的國家走在一條小路上。 你在一個岔路口遇到一個單槍匹馬的戰士。 岔路的每個分支都通向一個村莊。 你知道一條路通向一群總是說真話並會給你食物的和平人民。 另一條路通向一個天生的騙子村莊，他們會殺了你。 兩個村莊的人看起來很像。 你被允許向戰士問一個是非題，然後你必須選擇一個岔路口並迎接你的命運。 你應該問什麼問題？”
（在繼續閱讀之前先想出你自己的答案。）
問：“這個分支通向你的村莊嗎？”（同時指向一個分支）。
原因如下：假設你指向騙子的村莊。 騙子會否認你指向他的村莊，說真話的人也會否認。 如果你指向說真話的人的村莊，他們都會說他們來自那裡。 在任何一種情況下，你都知道你應該走哪條路。
亨利警官繼續說道：“問題是，我們大多數人在現實生活中認識的騙子只是偶爾說謊。 有時他們選擇說真話，有時他們說謊。 這似乎讓事情變得更容易，但事實並非如此。 如果例子中的戰士是一個偶爾說謊的人，他可能會告訴你去他真正的村莊來回答這個問題。”
“事實上，如果在一群戰士中最多隻有一個偶爾說謊的人，而其餘的人都說真話，那麼你需要至少三個戰士才能使用這個問題來確定該怎麼做。 大多數人會告訴你真相。”
“我的問題涉及犯罪現場，但我不能告訴你細節，因為它們是保密的，所以我們把它變成一個遊戲。 假設一個不透明的盒子裡有一個物體。 你知道它是一個物體，它可以是紅色或黑色，可以是大的或小的，可以是鞋子或襪子。 你想發現盒子裡是什麼。”
“有三個人見過這個物體。 最多有一個人是偶爾說謊者。 其他人都是誠實的。”
問題 1. 假設你可以問每個人最多三個是非題，前提是你總共提出的問題不超過七個。 你能弄清楚物體的尺寸、顏色和型別嗎？
“現在是更困難的問題：六個人見過盒子裡的物體。 最多有兩個人是偶爾說謊者。 其他人都是誠實的。”
問題 2. 你能問每個人最多兩個是非題，並弄清楚盒子裡是什麼嗎？
問題 3. 如果襪子只能是黑色的，而鞋子只能是大的，你能做得更好嗎？
解答： 1. 克洛伊幾乎立即回答道：“稱呼這些人 A、B、C。 詢問 A 和 B 關於尺寸； 如果他們意見一致，他們的答案是可信的。 詢問 A 和 B 關於顏色； 如果他們再次意見一致，那麼這個答案也是可信的。 詢問 A 和 B 關於物體，如果他們對物體也意見一致，那麼你只用六個問題就解決了問題。 現在假設 A 和 B 對他們對任何問題的答案都不同意。 這意味著 A 或 B 其中一人是偶爾說謊者。 立即向 C 提出相同的問題和任何剩餘的問題，C 的答案肯定是可信的。 如果 A 或 B 在尺寸或顏色上撒謊，你總是可以用最多六個問題來解決問題。 如果 A 和 B 在關於物體的問題之前都意見一致，那麼你將總共需要七個問題。”
2. 稱呼這些人 A、B、C、D、E、F。 詢問 A、B 和 C 關於尺寸。 如果沒有分歧，那麼詢問 D、E 和 F 關於顏色。 如果對顏色沒有分歧，那麼詢問任意五個人關於物體的型別（襪子或鞋子），並相信多數人的答案。 這種包含 11 個問題的場景結果是最糟糕的情況，即使可能沒有人撒謊。 當騙子早早出現時，需要的問題就更少，因為那時你可以將你的問題集中在說真話的人身上。
因為有很多情況，請考慮這個決策樹 (http://cs.nyu.edu/cs/faculty/shasha/papers/liars1.pdf) 的可能響應。 從頂部節點（根節點）開始，並沿著樹向下跟蹤每個結果。
3. 我不打算給你完整的解決方案，但考慮一下資訊理論方面的專家在這種情況下會怎麼做：首先解決不確定性最大的問題。 因此，首先詢問 A、B 和 C 關於鞋子或襪子的問題。 如果你得到一致性，那麼你只需要詢問另一個屬性。 另一個屬性已經是已知的。 你能從這裡繼續下去嗎？