百科问答小站 logo
百科问答小站 font logo



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

  

user avatar   jiao-zi-nan-89 网友的相关建议: 
      

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

  • 若 且 ,则 ;
  • 若 ,则 ,

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

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

就称 是 上的超滤子(ultrafilter)。

若 是无穷集,容易验证 的所有余有限子集(即:有限子集的补集)组成一个滤子,称为余有限滤子。

接下来要用一个定理(该定理依赖选择公理):

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

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

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

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




  

相关话题

  以π指代圆周率是偶然的约定俗成还是特别的另有深意? 
  函数方程 f(xy)=f(x)+f(y) 的严格解是什么?解是否唯一? 
  能否通过逻辑编程消灭程序BUG? 
  如果变量X Y独立怎么证明E(X+Y)=E(X)+E(Y),E(XY)=E(X)E(Y)? 
  如何证明这道有关叉乘的解析几何题? 
  为什么做数学题时,自己想不出来,而翻到后面看答案解析时却全都能能看懂? 
  印刷体的数学符号在手写的时候有哪些规范? 
  如何看待菲尔兹和阿贝尔奖双料得主 Michael Atiyah 宣称自己证明了黎曼猜想? 
  阿基里斯和乌龟的悖论真的不能用常规逻辑推翻吗? 
  在高中,数学不好的人物理一定也不好吗? 

前一个讨论
对于俄乌战争,你支不支持美国?
下一个讨论
如果把一首小调曲子里每个句末的la都改成do,曲调会变成大调吗?





© 2025-04-24 - tinynew.org. All Rights Reserved.
© 2025-04-24 - tinynew.org. 保留所有权利