100名囚犯猜红绿灯，最多能保证多少人猜对？ 第1页

首先补充一些概念：给定非空集合 ，设 是 的一些子集组成的集合，若满足条件

• ；
• 若 且 ，则 ；
• 若 ，则 ，

就称 是 上的滤子（filter）。由定义立即可知对任意 ， 不能同时成立（ 是 在 中的补集）。若还满足条件

• 对任意 ， 有且仅有其一成立，

就称 是 上的超滤子（ultrafilter）。

若 是无穷集，容易验证 的所有余有限子集（即：有限子集的补集）组成一个滤子，称为余有限滤子。

接下来要用一个定理（该定理依赖选择公理）：

任意滤子可以扩充为一个超滤子，即若 是 上的滤子，则存在 上的超滤子 满足 。

取 ，记 是 的余有限滤子，将其扩充为超滤子 ，游戏开始前每个囚犯都记住这个 。游戏开始后每个囚犯观察屋里绿灯亮、红灯亮的时刻，分别记为集合 和集合 ，这两个集合互补，因此 有且仅有其一成立。如果是前者成立，囚犯就猜绿灯模式，反之就猜红灯模式。

下面说明至多有一人猜错。假设有两人猜错，不妨设国王选择绿灯模式，而这两人都猜红灯模式，记它们的红灯集为 ，则 ，于是 。但是在绿灯模式下两个人不能同时看到红灯，而自由模式只有有限次亮灯，故 是有限集，从而根据构造， 作为余有限集也属于 ，矛盾。

于是（在选择公理成立的前提下）存在能保证 99 人猜对的策略。另一方面，显然不存在能保证 100 人猜对的策略（囚犯若看到“绿红绿红绿红……”，则无法分辨是绿灯模式还是红灯模式），因此 99 人就是最好的结果了。