在 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 日左右公布。