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



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

  

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

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

  • 若 且 ,则 ;
  • 若 ,则 ,

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

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

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

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

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

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

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

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

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




  

相关话题

  如何理解微分几何中的『联络』? 
  已知 a、b、c 为实数,且三个数的和为 1,平方和也为 1,如何求三个数的立方和的最小值? 
  康托尔著名的对角线证明? 
  近期汤加火山喷发喷出了多少立方千米喷出物? 
  级数加括号后发散,是否之前一定发散? 
  你知道哪些冷门但内容十分好的数学书? 
  理想情況下,对于任意一种台球布局,是否存在一个击球方案,一杆就能使所有球进洞? 
  怎么样是物理地物理? 
  函数求导的逆运算? 
  为什么许多人建议本科学数学,研究生阶段转金融或者计算机?学数学的发展方向只有纯数学计算机以及金融吗? 

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





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