猫猫帽子谜题
前两天看到一道有意思的帽子谜题，分享一下。
题目
将十个人排成一行，主持人给他们每个人头上带上 黑色 或 白色 的帽子。他们每个人只能看到自己前面人的帽子颜色。主持人要求从最后一个人开始依次猜测自己头上的帽子颜色，至少要有 9 个人猜对自己头上的帽子颜色。
他们在开始之前可以交流商量策略，那么有什么策略能够满足要求呢？
虽然同样是帽子谜题，这可比「我不知道我的颜色」「我知道你不知道」「那我知道了」这种题目有意思多了。
提示
显而易见的一点是，第一个猜的人一定会被牺牲，也就是说后面的 9 个人都要能猜出自己的帽子颜色才行。
我的第一反应是：每个人告诉别人自己前面人他的帽子颜色不就行了？ 但实际上，这也正是这道题有趣的地方。
这个策略是不行的。
一个似乎矛盾的点是：
- 每个人只能提供 1 比特的信息，而每个人猜对也同样需要 1 比特，因此所有信息都必须派上用场；
- 除了第一个人，后面的人只能回答自己帽子的颜色，而自己帽子的颜色和下一个人帽子的颜色之间是无关的。
换句话说，后 9 个人只能提供 局域 的信息，他们提供的信息对别人没有帮助。因此，破局的点就是：
第一个人提供的信息应该是 全局 的，这样才能让后面所有人帽子的状态发生「纠缠」。
更进一步的提示
实际上，这个问题有一种更简单的等价陈述。如果我们的策略是成功的，那么后面的 9 个人通过听和看，都能知道其他 8 个人的帽子颜色，因此，这个谜题的本质是：
- 9 个人每个人带着一顶 黑色 或 白色 的帽子；
- 每个人都能知道其他 8 个人帽子的颜色；
- 某个上帝1提供 1 比特的信息，让所有人都能猜对自己帽子的颜色。
再结合刚刚的分析，这 1 比特信息应该是用于描述 这 9 个人帽子的整体状态 的。这样一来，每个人就只需要回答
「其他人的帽子状态和上帝给出的总状态之间差了一顶什么颜色的帽子？」
就可以知道自己帽子的颜色了。
答案
因此，答案是？
新的问题
如果有 (可数) 无穷 数量的人参加游戏, 其他条件依然不变, 能否设计一种策略, 可以让除了第一个人以外的所有人猜中自己头上的帽子颜色呢?
为了让这个问题更便于讨论, 我们把它翻译为数学语言. 根据上面的分析我们已知, 如果把第一个人排除在外, 每个人实际上都能知道除自己以外所有人帽子的颜色. 第一个人做的就是根据所有人的帽子颜色给出一个 0 或 1 的信息, 要使得每个人都能通过这个信息推断出自己帽子的颜色. 因此这相当于给出一个函数
\[f:\quad \{0,1\}^{\mathbb{N}} \to \{0,1\},\]并要求对任意 $n\in\mathbb{N}$, 翻转第 $n$ 位将会输出不同的结果
\[f(a_1,\cdots,a_n,\cdots) \ne f(a_1,\cdots,1-a_n,\cdots).\]另一种写法是
\[f(x\oplus e_n) = f(x)\oplus 1,\]这里 $\oplus$ 表示异或运算, 而 $e_n = (0,\cdots,0,1,0,\cdots)$ 是只有第 $n$ 位为 1 的序列2.
思路
首先我们会意识到, 奇偶性作为判据在这个例子中不适用. 我们的无穷求和很有可能是发散的
\[1 + 1 + 1 + \cdots \equiv \text{未定义} \quad(\mathrm{mod}~2).\]尽管如此, 这仍然可以给我们提供宝贵的思路. 有些读者可能会思考这样一个问题:
如果两个序列之间相差无穷多位, 或者说需要无穷多次翻转才能相互转化
\[(a_1,a_2,a_3,0,1,0,1,\cdots) \leftrightarrow (a_1,a_2,a_3,0,0,0,0,\cdots),\]就说明 $f(abc0101\cdots)$ 和 $f(abc0000\cdots)$ 之间的差值应该是 $\infty\equiv\text{未定义}~(\mathrm{mod}~2)$. 这实际上就是在说, $f(abc0101\cdots)$ 和 $f(abc0000\cdots)$ 其实可以是相互独立的结果.
确实, 我们对 $f$ 的约束只是在于: 当两个序列相差 有限位 时, 它们的输出也应该翻转对应的次数. 如果两个序列相差 无穷位, $f$ 的输出其实就没有限制了. 直观上来看, 两个「尾巴」不同的序列位于 $f$ 的两个独立的互不联通的分支上, 我们只要根据「尾巴」前面的有限个数位计算 $f$, 而不同分支的 $f$ 互不影响.
一种依赖选择公理的构造
以上思路很清晰, 唯一的问题是对于「尾巴」的定义并不严谨. 读者可能会担心:
真的可以把所有序列按照「尾巴」不同, 分类进不同的分支吗?
这是以上思路的核心, 幸运的是, 仔细思考后我们会发现这样的分类确实是可行的.
考察序列之间的等价关系: $\{a_i\}\sim\{b_i\}$ 当且仅当 $\{a_i\}$ 和 $\{b_i\}$ 之间相差有限位. 读者可以验证这确实构成等价关系3. 于是我们可以考虑这个等价关系构成的等价类
\[[a] = \big\{\{b_i\}\big|\{a_i\}\sim\{b_i\}\big\}.\]这就是所有和 $\{a_i\}$ 相差有限位的序列的集合.
由于等价类的性质, 同一个等价类中的序列之间一定只相差有限位, 而不同等价类之间的序列一定相差无穷位; 且等价类之间互不重叠, 把所有可能序列的集合 $\{0,1\}^{\mathbb{N}}$ 划分为了不同的分支.
于是, 每一个等价类内部我们可以独立地定义 $f$. 为此利用选择公理, 给每一个等价类找出一个代表元
\[[a] \mapsto \{a_i\}\in[a],\]我们就可以定义
\[f_{[a]}(b) = \sum_{i=1}^\infty (b_i - a_i) \quad(\mathrm{mod}~2).\]此时因为 $a$ 和 $b$ 在同一个等价类中, 这个无穷求和实际上只有有限项, 因此是良定义的. 最后, 只要拼接起所有的 $f_{[a]}$ 就可以得到我们所求的函数 $f$ 了.
更多关于此问题的阅读
和 ChatGPT 讨论解法时发现了一些严肃讨论该问题的文献:
https://www.math.uni-hamburg.de/home/geschke/papers/Choice_and_the_hat_game6.pdf
https://www.cs.umd.edu/~gasarch/TOPICS/hats/infinite-hats-and-ac.pdf
https://arxiv.org/pdf/2411.06002
如此等等. 第一篇文献指出这个问题不可能在 ZF 体系下被解答, 但同时也指出选择公理是不必须的, 我们可以通过某些弱化版本的选择公理解决该问题. 第二篇文献是对这类问题的综述.
原本只是在 B 站刷到了有限版本的这一问题, 没想到其背景这么丰富.