首先声明这并不是一篇标题党的文章，标题中的“世上最难”不是我说的，是 wikipedia 说的。故事的开始是苦逼的博士狗们一起赶作业，然后尘锐案突然就把这个东西搬了出来，然后大家瞬间两眼放光，纷纷抛弃了作业……当然主要的讨论都是由Y. Huang和尘锐案进行的，我只是听懂并且理解了他们的做法，不过实在是很有意思，所以记录一下.
问题
世上存在三个神，分别是 True 神，False 神和 Random 神。其中
- True 神只说真话
- False 神只说假话
- Random 神每次在听完问题后，抛一枚硬币来决定说真话还是说假话
它们现在就在你面前，但是你不知道哪个神是哪个神。你有三次机会来试探，每次机会你可以说出一个 statement，并找其中一位神来给出判断 (T/F)。 神总是能听懂你的语言，并给出按照它设定的回答，但是它会用自己的语言来回答，它会回答 X 或 Y 。你知道其中一个代表 T，另一个代表 F，但是并不知道哪个代表哪个。
问题来了：你能在用完三次机会后，判断出三位神各自的身份吗？
答案
答案是：可以。
甚至我们可以做到更强：每次都可以随机问一个神（特别的，可以做到每次都问同一个神，或者依次问完所有神）。事实上，我们有如下定理
而这个 $\mathrm{P}(Q)$ 的存在性，是我们反推出来的。当时的情况是：Y. Huang不知道从哪里知道了有这个定理，于是我们一起把这个 $\mathrm{P}(Q)$ 推导了出来。事实上，考虑这样一个图：$Q\rightarrow \mathrm{P}(Q)\overset{\text{God}}{\rightarrow} \{\text{X,Y}\}\overset{\mathrm{I}}{\rightarrow} \{\text{T,F}\}$。这里，God 箭头表示神给出了判断，$\mathrm{I}$ 是我们自己对神的语言的解释，我们希望最后这个复合函数给出了 $Q$ 的判断，也就是说，我们希望如下的复合是一个恒等映射
$$\{\text{T,F}\}\overset{\mathrm{P}}{\rightarrow} \{\text{T,F}\}\overset{\text{God}}{\rightarrow} \{\text{X,Y}\}\overset{\mathrm{I}}{\rightarrow} \{\text{T,F}\}$$
所以我们有 $\mathrm{I}\circ \text{God }\circ \mathrm{P} =\mathrm{id}$，我们对 God 函数唯一知道的事情是：它是一个双射。也就是说，它一定会把 T 映射到 X,Y 中的一个，然后把 F 映射到另一个。所以我们可以写下如下等式：$\mathrm{P}=\text{God}^{-1}\circ \mathrm{I}^{-1}$
我们好像几乎做完了（因为找到了 $\mathrm{P}$ 的表达式），但是又好像什么都没做（$\text{God}^{-1}$ 是个什么鬼！）
我们作如下观察：
- $\mathrm{I}$ 是我们自己选择的解释，所以我们可以给出自己的规定，比如：$\mathrm{I}(\text{X})=\text{F},\mathrm{I}(\text{Y})=\text{T}$。也就是说，God 说 X，我们就认为它说 F；God 说 Y，我们就认为它说 T。
- 假如 $\mathrm{I}\circ \text{God }\circ \mathrm{P}$ 把 T 映射到 T ，那么它已经是个恒等映射了。因为每一步都是双射，而一共只有两个元素，只要一个元素对，另一个元素就一定是正确的。
所以我们只需要 $\text{God}\circ \mathrm{P}(\text{T})=\mathrm{I}^{-1}(\text{T})=\text{Y}$，下面是睁大眼睛的时刻：
假如 $\mathrm{P}(\text{T})$ 是 true statement， 也即 $\mathrm{P}(\text{T})=\text{T}$，我们有如下等价
$$\mathrm{P}(\text{T})\Leftrightarrow \mathrm{P}(\text{T})=\text{T} \Leftrightarrow \text{God}(\mathrm{P}(\text{T}))=\text{God}(\text{T}) \Leftrightarrow \text{Y}=\text{God}(\text{T})$$
所以！$\mathrm{P}(\text{T})$ 这个 statement 就是在说 $\text{God}(\text{T})=\text{Y}$，翻译一下就是：你对 truth 的判断是 Y。
我们来考虑一下真值表，假设神的语言是 X 代表 T，Y 代表 F:
- 假如是 True 神，那么对它来说： truth 的判断是 X。所以我们的 statement 是假的，从而它要说Y。经过我们的解释函数 $\mathrm{I}$，我们得到了回答 T。
- 假如是 False 神，那么对它来说：truth 的判断是 Y。所以我们的 statement 是真的，从而它要说Y。经过我们的解释函数 $\mathrm{I}$，我们得到了回答 T。
现在我们可以把 T 换成我们想要的任何 statement $Q$ 了。比如，$Q$ = 你是 True 神。延续上面的语言设定（X for T，Y for F），那么我们问神的 statement 是：你对“你是 True 神”的判断是 Y，然后
- 假如是 True 神，那么 $Q=\text{T}$，根据我们上面的分析，我们可以得到 T 的回答，注意这个 T 是针对 $Q$ 的判断，所以我们知道这个神就是 True 神
- 假如是 False 神，那么 $Q=\text{F}$，所以它对 $Q$ 的判断是 X。再看我们的 statement，发现我们的 statement 也是假的，所以它要说反话，从而给出 X 的回答，而我们的翻译（注意这里是 $\mathrm{I}$ 函数而不是上面的语言设定）说 X 代表 F，所以这个不是 True 神
- 假如是 Random 神，那么 $Q=\text{F}$。假如它选择说假话，那么和 False 神一样的推出它的回答是 X ；假如它选择说真话，那么它对 $Q$ 的判断是 Y，从而我们的 statement 是对的，所以它会说 X。但是解释函数告诉我们，这意味着 $Q$ 是假的，所以这个也不是 True 神！
我们看到，只有 True 神会给出 T 的回答，其余都是 F，所以接下来我们只要一个个问就行了。
推广问题
上述问题中，Random 神是在回答问题前，选择接受 True 神或者 False 神的设定，再作回答。可以看到我们的答案完全可以忽略 Random 神，因为当它抛完硬币后，它就被归到 True 神或者 False 神的情况里。所以呢，Random 神很不高兴，现在它要秀一下存在感：它决定通过抛硬币来决定它的回答（而不是回答方式）！也就是说，每次 Random 神给出的判断完全就是抛硬币的结果，而和你问什么完全没有关系。它完全不给出任何信息量。现在还是三次机会问三个神，请问：你还可以找到一个方法区分这三位神吗？
尝试解答
在 Random 神决定再也不当它们中的任何一个后，它就彻底不提供任何信息量了。那我们该怎么办呢？
注意：以下所有提问，均指用 $\mathrm{P}$ 函数包装过后再提问，就是当我们说提问 $Q$ 的时候，实际上我们在问 $\mathrm{P}(Q)$。
我们把三个神标注成 A、B、C，考虑问 A 神这样一个 statement：“B 是 Random 神”，会发生什么？
- 假如 A 是 True/False 神，B 不是 Random 神，那么 A 会告诉你：F
- 假如 A 是 True/False 神，B 是 Random 神，那么 A 会告诉你：T
- 假如 A 是 Random 神，那么 A 会告诉你：F 或者 T
有人说，这有啥用啊？T 和 F 都会出现，你还是啥都不知道啊？且慢，让我们仔细分析一下。假如答案是 T，那么只可能是
- A 是 Random 神
- A 是 True/False 神，B 是 Random 神
无论哪种情况下，C 神都不是 Random 神！同理假如答案是 F，那么可以得出 B 神一定不是 Random 神！所以无论怎样，你都可以确定某一位不是 Random 神，接下来，只要对那位不是 Random 神的神问两问题：
- 谁是 Random 神
- 你是什么神
就可以了。具体怎么问，大家可以自己思考一下。
更变态的版本
我们看到，上面的解决方案依赖两点：
- 你不能只问一个神
- 你可以问同一个神两个问题
那就自然想到，能不能给这些东西加上限制：
首先想到的限制是：能不能只提问一个神？而这个限制显然是不可能的，因为运气不好可能正好抽到只提问 Random 神，那么无论你怎么发问都无法得出任何有效信息，此题无解。
那么第二个可能的限制是：能不能强制要求依次提问三个神（也即每次必须询问不同的神）？我们几个的 naive 想法是：不行，因为第一个问题只能确定 $0.5$ 个神的身份（也即是其中一个神不是 Random 神）。接下来我们必须利用这个神不是 Random 神这一点来拷问得到所有信息。假如必须依次提问，可能出现两种情况：
- 先问 Random 神，再问 True/False 神，最后问 False/True 神。
- 先问 True/False 神，再问 False/True 神，最后问到了 Random 神。
第一种情况自然皆大欢喜，你从一个本来不能获得任何信息的 Random 神那里获得了信息，所以绝对是可以完成任务的。但是第二种情况就有点无解了，最后一个问题没有办法给出更多的信息了。
一个具体的情形如：A 是 True 神，B 是 False 神，C 是 Random 神。我们先问了 A：B 是 Random 神吗？得到 F 回答，于是确定 B 不是 Random 神，接下来问 B：C 是 Random 神吗？（或者 A 是 Random 神吗？），得到回答可以让我们确定 C 是 Random 神，A 和 B 是 True/False 神。但是最后一个问题要问 C，而这种情况下我们是没有办法获得对 A 和 B 的信息的。