Table of Contents
题目
背景与问题113：Hats and Infinity完全一致：无穷多名囚犯，编号为\(1,2,3,\ldots\)，每人戴上一顶红帽或黑帽；亮灯后每个人都能看到其他所有人的帽色（但之后不允许交流），随后每名囚犯被单独带离并回答自己帽子的颜色。这次目标不同：
囚犯们的猜测必须要么全对，要么全错。是否存在必胜策略？
分析
答案是：存在。 与问题113一样，策略依赖选择公理（Axiom of Choice），本质上是非构造性的。耐人寻味的是，这个看起来"更苛刻"的目标（只有"全对"或"全错"两种结局）反而可以用问题113的同一套代表元机器，加上一个奇偶性技巧就实现。
一、有限情形的启发
先看有限情形：若有\(n\)名囚犯，只需约定"假设红帽总数为偶数"：
- 每个囚犯数自己看到的红帽数：若为奇数就猜自己是红帽，否则猜自己是黑帽。
这样若真实红帽总数为偶数，则每个囚犯的推断都与实际一致——全体猜对；若为奇数，则每个囚犯的推断都与实际恰好相反——全体猜错。
所以任意有限数量的囚犯都能轻松保证"全对或全错"。（这正是问题087：Half-Right Hats中"恰好一半人猜对"的同一技巧，只是这次要的是"要么全体、要么全无"。）
二、无穷情形的困难与出路
囚犯有无穷多个时，"红帽总数"可能为无穷，奇偶性失去了意义。出路在于把奇偶性放进每个等价类内部：
两个分配\(x,y\)称为等价（\(x\sim y\)），当且仅当它们仅在有限多个位置上不同。
由选择公理，在每个等价类\(S\)中选定一个代表元\(r(S)\)，全体囚犯在商议阶段记住这个代表元族（与问题113完全相同）。
三、策略：按"与代表元差异数的奇偶"猜测
囚犯\(k\)看到除自己外的所有帽色。无论他自己的帽色是红还是黑，补全后的完整序列都落在同一个等价类\(S\)中——改变一个位置不会改变等价类。于是他确定\(S\)，查表得到代表元\(r=r(S)\)。
接着他做如下推理。设真实分配\(x\)与代表元\(r\)的差异数为
\[ d=\left|\{i: x_i\neq r_i\}\right|,\]
这是一个有限的数。囚犯\(k\)虽不知道\(x_k\)，但能算出除自己外的差异数
\[ d_k=\left|\{i\neq k: x_i\neq r_i\}\right|.\]
于是只有两种可能：
- 若\(x_k=r_k\)，则\(d=d_k\)；
- 若\(x_k\neq r_k\)，则\(d=d_k+1\)。
两种可能的\(d\)正好相差\(1\)，一奇一偶。囚犯\(k\)的猜测规则是：
猜那个使得总差异数\(d\)为偶数的帽色。
即：若\(d_k\)为偶数，猜自己的帽色与\(r_k\)一致；若\(d_k\)为奇数，猜自己的帽色与\(r_k\)相反。
四、为什么有效
每个囚犯都独立执行同一规则："让自己的帽色恰使整体的差异数\(d\)为偶数"。因此结果只取决于真实差异数\(d\)的奇偶：
- 若\(d\)为偶数：每个囚犯的猜测都正确——全体猜对；
- 若\(d\)为奇数：每个囚犯的猜测都与实际相反——全体猜错。
无论\(d\)的奇偶如何，恰好满足"全对或全错"。\(\square\)
五、结构注记
- 与问题113一样，该策略完全非构造性：选择公理只断言代表元族存在，任何有限程序都无法实际选出它。策略在数学上"存在"，但不可操作。
- 抽象的刻画：定义\(\sigma(x)=(-1)^{d(x,\,r(x))}\)为分配\(x\)的"相对奇偶"。若\(x\)与\(x'\)仅在第\(k\)位不同，囚犯\(k\)在两种情形下看到的是完全相同的画面，因此他的猜测相同，故\(\sigma\)在两个相邻分配上取值必然相反。在无穷超立方体上，这种"相邻相反"的赋值在每个等价类内独立选取基准值即可得到；反过来，任何这样的赋值都对应一个获胜策略（每个囚犯猜使\(\sigma=+1\)的那个补全）。这正是获胜策略存在的等价刻画。
- 一个钻空子的"更简单解法"：让所有囚犯都猜"绿色"！帽子只有红黑两色，于是每个人都必然猜错，"全错"自动满足。若规则要求答案必须是红或黑之一，则代表元方案才是正经答案。