囚徒帽子（无限人）
Prisoner's Hat (Infinity)
题目详情
有可数无限多名囚徒排成一列，每人帽子是红或蓝，随机赋值。
每个人只能看到自己前方所有人的帽子，看不到自己与身后。队尾开始依次报出自己帽色，报错当场处死。
囚徒可事先商量，但一旦排队后 任何人都听不到别人说的话。
问：是否存在策略，保证只有有限名囚徒会被处死？
A countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed?
解析
存在（需要使用选择公理的构造）。
把所有“无限长二进制串”（红/蓝序列）按如下关系分成等价类：若两串只在有限多个位置不同，则视为等价。
从每个等价类中选取一个代表串 （选择公理）。排队时，第 个囚徒能看到前方帽子，从而确定自己所处等价类并知道代表串 ，于是他报出 的第 位作为自己的猜测。
真实序列与 只在有限多处不同，因此最多只有有限人报错。
Original Explanation
Solution
It uses Axiom of choice in a special way. Before night of execution, prisoners will create some equivalent classes among the set of all possible infinitely long binary strings. Let us say two infinite strings s1 and s2 are related, if they differ at finitely many places, and are same otherwise. This creates the equivalence relation. Thus they create all equivalence class. From each class, we mark one representative string.
Now, a person pi looks ahead, and instantly knows his equivalent class & recalls the representative string S. When his turn comes, he speaks the ith digit of S as his guess. Since S and actual (current) string only differ upto a finite (say N) number of position. Thus only atmost N people may die using this technique.
Now, first person will count number of places S differs from current string, and answer it in modulo 2. Based on answer of first person, second person can deduce his hat color. now the third person can deduce his color and so on. Except possibly for the first person, everyone will guess correctly.