求解三神问题 | Dale 的花园 ^

🦉

你降临到一个陌生的星球，这颗星球上有三位神，祂们的身份是：

真神：永远说真话

假神：永远说假话

任意神：随机决定说真话或说假话

三神只回答"Da"或"Ja"两个词. 其中一个表示"是"，另一个表示"否"，但你不知道神的语言哪个表示"是"，哪个表示"否".

三位神互相知道彼此的身份，你可以向祂们提问三次，每个问题必须是只能回答"是/否"的问题; 每次提问只能向其中一个神提问, 可以多次向一个神提问.

请通过三次提问，确定谁是真神、谁是假神、谁是任意神.

信息熵：判断求解可能性

我们之前在

Dale 的花园 ^_^有趣的信息熵 | Dale 的花园 ^_^

有趣的信息熵 | Dale 的花园 ^_^

信息是能够用来消除不确定性的东西

中介绍过信息熵：

考虑三神问题：三神的排列有 3! = 6 种可能性; 因此信息熵为

每一次提问只能得到 yes or no 的回复，所以一次提问能获得的信息熵

最理想的情况下，每次提问都可以获得 1 bit 信息熵，设提问次数为 n,

求解问题需满足：, n 为整数，所以

从信息熵计算看：三次提问可以确定三神的排列情况，问题有解.

但是！题干中说了：我们不知道神的回答 Da 和 Ja 对应 yes or no，这是一个独立因素，如果我们需要搞清楚 Da 和 Ja 的属性，那么三神问题的信息熵就会变得更大：

如果我们需要分清楚三神的排列情况和 Da/Ja 的属性，设提问次数为 m,

, m 为整数，所以

所以：分清楚三神排列和 Da/Ja 的属性，至少需要四次提问.

题干中说了：提问三次，确定 A、B、C 谁是真神、谁是假神、谁是任性神. 根据信息熵的计算，我们可以得到结论：三次提问能求解问题，但无法额外知道 Da/Ja 属性；所以，我们需要在根本不知道神的回答 Da/Ja 是 yes 还是 no 的情况下求解三神排列.

函数设计

我们先不考虑怎么用自然语言向神提问，而是将神抽象为函数表达.

定义三个简单函数

诚实函数, 接收什么就输出什么:

欺骗函数, 接收什么就反着输出什么：

任意函数, 随机输出 T 或 F：

显然：三神中真神执行 honest 函数；假神执行 cheat 函数；任意神执行 random 函数.

当我们提问一个简单命题，比如 ‘一加一等于二吗？’, 神的回答是让我们捉摸不透的，为了获得一些有用的信息，我们需要拼凑或发明一些复杂的函数来对付神.

我们问神的问题必须有 yes or no 的属性，很多逻辑函数也满足这样的要求，所以三神问题可以表达为：我们创造一些输出值为 yes or no 的逻辑函数，让神来执行, 确保神的回答能输出足够多的信息熵.

同或函数

定义同或函数 compare，此函数能接收两个变量，输出一个结果，规则为：

复杂函数 assume

函数定义

定义函数 assume，其能接收三个变量 R, prp, god

变量 R 代表 Da 的 T 或 F 属性

变量 prp 为一个朴素的二元命题：答案为 yes or no, 比如 ‘一加一等于二吗？’

变量 god 代表回答问题的神

函数表达式为：

以上 godAnswer 函数表示神接收一个命题，其所执行的函数：

对于真神, godAnswer 为诚实函数 honest

对于假神, godAnswer 为欺骗函数 cheat

对于任意神, godAnswer 为任意函数 random

将 assume 函数翻译为自然语言，可表述为: ”假如我问你 “[朴素二元命题 prp]”, 你的回答会是 Da 吗？”.

举例1: 询问真神 “假如我问你 ‘一加一等于二吗’, 你的回答会是 Da 吗？”. 那么真神的回答一定是 Da, 无论 Da 在神的语言里表示 yes 还是 no.

举例2: 询问假神 “假如我问你 ‘一加一等于二吗’, 你的回答会是 Da 吗？”. 那么假神的回答一定也是 Da, 无论 Da 在神的语言里表示 yes 还是 no.

assume 函数的输出表

assume 函数接收三个自变量：R 的取值只有 T/F 两项; prp 的取值只有 T/F 两项; god 的取值只有真神假神任意神三项. 我们现在制作 assume 接收不同变量值的输出表：

R	prp	god	assume 输出值	assume 输出值翻译为神的语言
T	T	真神	T	Da
T	T	假神	T	Da
T	T	任意神	T or F	Da or Ja
T	F	真神	F	Ja
T	F	假神	F	Ja
T	F	任意神	T or F	Da or Ja
F	T	真神	F	Da
F	T	假神	F	Da
F	T	任意神	T or F	Da or Ja
F	F	真神	T	Ja
F	F	假神	T	Ja
F	F	任意神	T or F	Da or Ja

assume 的性质

观察以上表格，提取出 assume 函数的性质:

当神调用 assume 函数时，无论 Da 的属性是 T 还是 F，只要命题 prp 为真，真神和假神都会回答 Da; 只要命题 prp 为假，真神和假神都会回答 Ja. ——【定理1】

所以 assume 函数的作用就是：抹平真神和假神对同一问题的输出, 排除干扰.

当然 assume 函数对任意神是无效的, 我们需要通过推理来找到任意神.

第一个问题

三神从左到右依次为 A、B、C，我们不知道祂们的身份，但祂们彼此知道.

提问 A：”假如我问你 “祂（手指向B）是任意神”, 你的回答会是 Da 吗？”

这个提问就相当于让 A 执行 assume 函数：

R 可能是 T 也可能是 F

god 可能是真神、假神或任意神

命题 prp 是 “B是任意神”

现在分两种情况讨论：

情况一: A 不是任意神

这种情况下 A 是真神或假神.

根据【定理1】: 若 prp（“B是任意神”）为真, A 会回答 Da; 若 prp 为假, A 会回答 Ja.

也就是说: A 回答 Da 就说明 B 是任意神; A 回答 Ja 就说明 C 是任意神.

也就是说: A 回答 Da 就说明 C 不是任意神; A 回答 Ja 就说明 B 不是任意神.

情况二: A 是任意神

不管 A 回答 Da 还是 Ja, B 和 C 都不是任意神

综合以上情况一和情况二:

不管哪种情况，只要 A 回答 Da, C 就不是任意神；只要 A 回答 Ja, B 就不是任意神.

第一个问题的收获: 明确了三神中的某一位，祂不是任意神. 剩下两个神未知.

第二个问题

假设第一个问题后我们知道了 C 不是任意神，那么:

提问 C: “假如我问你 “祂（手指向B）是任意神？”, 你的回答会是 Da 吗？”

根据【定理1】: 若 prp（“B是任意神”）为真, C 会回答 Da; 若 prp 为假, C 会回答 Ja.

也就是说: 如果 C 回答 Da, B 就是任意神, 那么 C 肯定是假神；如果 C 回答 Ja, B 就不是任意神, 那么 B 是假神, C 是任意神.

第二个问题的收获: 明确了三神中任意神是哪一位，剩下两位身份未知，但一个真神一个假神.

第三个问题

假设第二个问题后我们知道了 A 是任意神，那么:

提问 C: “假如我问你 “你是真神？”, 你的回答会是 Da 吗？”

根据【定理1】: 若 prp（“C是真神”）为真, C 会回答 Da; 若 prp 为假, C 会回答 Ja.

也就是说: 如果 C 回答 Da, 祂就是真神；如果 C 回答 Ja, 祂就是假神.

也就是说: 回答 Da: C 是真神，B 是假神；回答 Ja: C 是假神，B 是真神.

第三个问题的收获: 明确了三神的身份.

实际上: 第二个问题和第三个问题也可以顺序互换. 通过三轮提问我们最终解决了三神问题.

🦉

三神问题的灵感来自 Smullyan 设计的一系列 “Knights and Knaves” 问题. 后来 John McCarthy 在这些问题的基础上增加了一个限制：你听不懂神的语言. 1996 年，George Boolos 发表文章《The Hardest Logic Puzzle Ever》，正式提出了三神问题.

the end.