在 19 世紀初，廷巴克圖的存在在歐洲人中仍然存疑。關於其巨大財富的故事驅使許多人試圖到達這座傳說中的城市。不幸的是，進入現在馬裡北部地區對外界人士來說是禁區。帶著大量資金、武器和錯位的信心出發的探險隊遭到襲擊，領隊通常被殺或被奴役。那不是一個溫和的時代。
勒內·卡耶是一位來自法國的赤貧孤兒，他沒有資源來組織探險。所以他嘗試了一種不同的策略。他學習了阿拉伯語和伊斯蘭文化，並以皈依者的身份加入了各種商隊。這克服了宗教障礙，但一個孤獨的旅行者總是容易被奴役或被盜。這完全是一個信任誰的問題。
對於我們的謎題，想象一下存在一個熟人拓撲（即誰認識誰的地圖）。你的對話者知道拓撲結構，但只知道他們可以指向你的人（透過箭頭）的可靠性和地址。
關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保關於當今世界塑造的發現和思想的具有影響力的故事的未來。
例如，考慮下圖
http://cs.nyu.edu/cs/faculty/shasha/papers/Caillefig1.doc
最左邊的圓圈，標記為 A，是你拜訪的第一個人，假設在桑巴蒂基拉（象牙海岸）。每個垂直的形狀集合代表一個引薦級別，標記為 A 到 D。A 中的人知道 B 級兩個人的可靠性和他們的地址，所以她把你送到其中一人。B 級的人把你送到 C 級的人那裡（總是沿著箭頭走），C 級的人把你送到 D 級的人那裡。D 級的人可能會幫助你，也可能會奴役你。
在你出發之前，你知道 A、B 和 C 級（圓圈）中的一個人可能是壞人。
熱身
除了圓圈中可能有一個壞人之外，D 級方塊中的多少人必須是好人才能確保你沒有真正的風險？
熱身解答
如果 D 級的四個方塊中有三個是好的，那麼在下半部分或上半部分中至少有一個好方塊。如果 A 是壞人，那麼你在 B 級和 C 級遇到的人會將你引向 D 級的一些好方塊。如果 A 是好人，那麼他會將你引向一個誠實的 B，他會將你引向一個誠實的 C，然後 C 會將你引向 D 級的一些好方塊。
你發現拓撲結構已更改為你在此圖中看到的
http://cs.nyu.edu/cs/faculty/shasha/papers/Caillefig2.doc
即使 A、B 和 C 級中只有一個騙子，也必須至少有五個方塊是好的，才能在你到達 D 級時確保安全。原因是，如果只有四個或更少的方塊是好的，那麼它們可能都在，比如，在下半部分。如果 A 級的圓圈是壞的，那麼他可能會把你引向上半部分，那時你將毫無希望。
問題： 1。假設在 A、B、C 級的所有圓圈中有一個壞人（但你不知道是誰），並且在 D 級有三個壞人（你也不知道是誰），對於這張圖
http://cs.nyu.edu/cs/faculty/shasha/papers/Caillefig2.doc
你是否保證最終會遇到一個好人？
2. 假設這張圖的拓撲結構
http://cs.nyu.edu/cs/faculty/shasha/papers/Caillefig3.doc
為了確保你的安全，D 級可能有多少個壞人？
3. 繼續上一個問題的圖的拓撲結構：假設如果你的當前對話者告訴你前面有危險，我們允許你返回到你之前訪問過的人。當然，他可能在撒謊。然而，我們假設每個線人都知道他指向的兩個人和指向他的人的善良狀態。如果在 D 級有三個騙子，但在 A、B 和 C 級中只有一個，你能確定在 D 級找到一個好家嗎？
答案將在 10 月 19 日左右公佈。