克洛伊刚从她的长曲棍球比赛回来，她的双胞胎弟弟泰勒就打来了电话。“亨利警官想过来。看来他要处理一些不可靠的目击证人，” 泰勒在她接起电话后告诉她。
亨利警官对于这两个十二岁的孩子来说是一个熟悉的人物，他已经开始依赖他们帮助处理棘手的案件。他自己也是一个聪明且认真的谜题研究者，他通常以给双胞胎们上一堂简短的历史课来开始他的案情介绍。
“在许多经典的谜题中，人们要么总是说真话，要么总是说谎，” 他开始说。“你问他们问题，要么你确定谁是说谎者，要么你在不明确确定任何人的诚实度的情况下发现一些事实。”
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。 通过购买订阅，您正在帮助确保有关塑造我们今天世界的发现和想法的有影响力的故事的未来。
“例如，这是我认为经典的谎言问题中的女王。 你在一个陌生的国家走在一条小路上。 你在一个岔路口遇到一个单枪匹马的战士。 岔路的每个分支都通向一个村庄。 你知道一条路通向一群总是说真话并会给你食物的和平人民。 另一条路通向一个天生的骗子村庄，他们会杀了你。 两个村庄的人看起来很像。 你被允许向战士问一个是非题，然后你必须选择一个岔路口并迎接你的命运。 你应该问什么问题？”
（在继续阅读之前先想出你自己的答案。）
问：“这个分支通向你的村庄吗？”（同时指向一个分支）。
原因如下：假设你指向骗子的村庄。 骗子会否认你指向他的村庄，说真话的人也会否认。 如果你指向说真话的人的村庄，他们都会说他们来自那里。 在任何一种情况下，你都知道你应该走哪条路。
亨利警官继续说道：“问题是，我们大多数人在现实生活中认识的骗子只是偶尔说谎。 有时他们选择说真话，有时他们说谎。 这似乎让事情变得更容易，但事实并非如此。 如果例子中的战士是一个偶尔说谎的人，他可能会告诉你去他真正的村庄来回答这个问题。”
“事实上，如果在一群战士中最多只有一个偶尔说谎的人，而其余的人都说真话，那么你需要至少三个战士才能使用这个问题来确定该怎么做。 大多数人会告诉你真相。”
“我的问题涉及犯罪现场，但我不能告诉你细节，因为它们是保密的，所以我们把它变成一个游戏。 假设一个不透明的盒子里有一个物体。 你知道它是一个物体，它可以是红色或黑色，可以是大的或小的，可以是鞋子或袜子。 你想发现盒子里是什么。”
“有三个人见过这个物体。 最多有一个人是偶尔说谎者。 其他人都是诚实的。”
问题 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 关于鞋子或袜子的问题。 如果你得到一致性，那么你只需要询问另一个属性。 另一个属性已经是已知的。 你能从这里继续下去吗？