12BET官方网 12BET官方网 12BET官方网 12BET官方网

科学与人文讲座2024年第21期报道: 一百囚徒与一个灯泡,及其他逻辑谜题

  • 图文/江丽莎
  • 创建时间: 2024-11-18
  • 147

2024年11月8日下午15点,2024年第21期“科学与人文”讲座在中国科学院哲学研究所报告厅举行。法国国家科学研究中心的Hans van Ditmarsch教授应邀开讲,讲座题为《一百囚徒与一个灯泡,及其他逻辑谜题》(One hundred prisoners and a light bulb-and other logic riddles)。12BET官方网范杰副教授主持了本次讲座。

讲座伊始, van Ditmarsch教授介绍本次讲座将主要涉及的逻辑谜题及其历史,他将详略有别地讲述七个谜题,分别是“泥孩(Muddy Children)”、“连续数(Consecutive Numbers)”、“和与积(Sum and Product)”、“俄罗斯纸牌(Russian Cards)”、“蒙提-霍尔(Monty Hall)”、“一百囚徒与一个灯泡(One Hundred Prisoners and a Light Bulb)” 以及“八卦(Gossip)”。

一、泥孩(Muddy Children)

Van Ditmarsch教授首先介绍了哈代(Hardy)和利特尔伍德(Littlewood)。哈代和利特尔伍德是 20 世纪英国数学家。其中哈代为普通读者撰写了《一个数学家的辩白》(A Mathematician's Apology)。利特尔伍德写了《数学家杂记》(A Mathematician's Miscellany)。哈代从一个重要的数学问题入手,利特尔伍德从 “泥孩”问题(现代)入手。

泥孩谜题:爱丽丝、鲍勃和卡洛琳在外玩耍后回到家,三个人脸上都沾了泥巴。父亲告诉他们,至少有一个人是泥孩,然后说:“某一刻我会击掌。如果你知道你自己是不是泥孩,请站出来。”他击掌,没有发生什么事情。他重复说两次。第三次击掌时,三个孩子都站了出来。解释这如何可能?

Van Ditmarsch教授认为解决这个谜题,可以描绘所有可能的情况。我们通过说明每个孩子是否是泥孩来确定一种情况。(“不是泥孩”与干净同义。)因此有八种情况。在下图中,一种情况用三个字节来表示。一个字节的值是0或1。如果爱丽丝是泥孩,那么第一个字节是1;否则,它的值是0。第二个字节代表鲍勃脸上的情况,第三个字节代表卡洛琳脸上的情况。例如,爱丽丝和鲍勃是泥孩而卡洛琳不是泥孩的情况用110来表示。

一些可能的情况用带标记的线连接起来。如果两种情况用带标记a的线连起来,那么爱丽丝(a)就不能区分这两种情况。例如,爱丽丝不能区分011和111,她不确定是否只有鲍勃和卡洛琳是泥孩还是她们三人都是泥孩。所以,这两种情况用a连起来。同样,爱丽丝不能区分的状态(a)、比尔不能区分的状态(b)或者卡洛琳(c)不能区分的状态,等等,都用线连起来。如果父亲说至少有一个人是泥孩,会发生什么?

现在父亲击掌,什么也没发生。父亲再次击掌,然而再次无事发生。只剩下一种情况 111。这里没有连线,没有可供选择的其他情况来考虑,所以三个孩子都知道他们都是泥孩。如果父亲现在第三次击掌,三个孩子都会站出来。

二、连续数(Consecutive Numbers)

Van Ditmarsch教授讲解了连续数谜题,并指出这个问题也被称为 “康威悖论”。

连续数谜题:安妮和比尔将分别被告知一个自然数,他们的数字相差为1。现在,这些数字正在他们各自的耳边悄悄响起。他们都知道这种情况。假设安妮被告知 2,比尔被告知 3。

下面是安妮和比尔之间的真实对话:

安妮:“我不知道你的数”。

比尔:“我不知道你的数”。

安妮:“我知道你的数”。

比尔:“我知道你的数”。

解释一下为什么会出现这种情况。

Van Ditmarsch教授解释如下。第一个宣告排除了数对(0,1),否则安妮知道比尔的数是1。第二个宣告排除了数对(2,1)。因为倘若比尔的数是 1,通过第一个宣告,他会排除安妮的数为0的情形,从而推出安妮的数是2,此时比尔知道安妮的数,由此比尔就会在第二个宣告中说他知道安妮的数,但是他没有那样说。然后,通过第三个宣告,确定得出数对(2,3)是真的,谜题就这样被解决了。四个宣告都是真实的宣告,因为这些宣告是在不同时刻做出的。

三、和与积(Sum and Product)

Van Ditmarsch教授讲解了和与积谜题:A 对 S 和 P 说:我选择了两个整数 x和y,其中1 <x < y且x+y≤100。我将只告诉S这两个数的和,只告诉P这两个数的积。需要确定数对 (x, y)。

现在进行如下对话:

  1. P 说:“我不知道”。
  2. S 说:“我就知道你不知道”。
  3. P 说:“我现在知道了”。
  4. S 说:“我现在也知道了”。

确定 (x, y)。

关于这个谜题,van Ditmarsch教授给出了分析思路。如果这两个数分别是 2和3,那么由于6=2*3和6=1*6,而这两个数都大于1,所以只可能是6=2*3。由此P可以根据它们的乘积推导出这对数。如果这两个数是质数,同理P 也能推导出这对数,因为对于质数来说,积的因式分解是唯一的。Van Ditmarsch教授鼓励同学们讲座后自行思考这一谜题。

Van Ditmarsch教授指出,这个谜题最初1969年由 Hans Freudenthal 以荷兰语撰写,后来经由 John McCarthy、Martin Gardner 等人的努力在人工智能领域流行起来。

四、俄罗斯纸牌(Russian Cards)

Van Ditmarsch教授简单介绍了俄罗斯纸牌谜题,指出这个谜题最早出现于1847 年托马斯-柯克曼(Thomas Kirkman)的《关于组合中的一个问题》(On a problem in combinations)中。

俄罗斯纸牌谜题:给定已知的七张牌 0、1、2、3、4、5、6 ,爱丽丝和鲍勃从中各抽出三张牌,凯茜得到剩下的一张牌。爱丽丝和鲍勃怎样才能公开地告诉对方自己的牌,而又不让凯丝知道他们拿到的任何牌呢?

五、蒙提-霍尔(Monty Hall)

蒙提-霍尔谜题又被称为“三门问题”。

蒙提-霍尔谜题:假设你在参加一个游戏节目,你有三扇门可以选择。一扇门后面是一辆汽车,其他两扇门后面是山羊。你选了一扇门,比如 1 号门,主持人知道门后是什么,他打开了另一扇门,比如 3 号门,里面有一只山羊。他对你说:“你想选2号门吗?” 换门对你更好吗?

向在场师生抛出问题后,van Ditmarsch教授紧接着给出自己的理解。汽车在 1 号门后面的概率是 1/3。如果你不换,你将赢得汽车;而如果换,那么你将失去汽车。此时你赢得汽车的概率是 。汽车不在1号门后面的概率是2/3。如果你不换,你将失去汽车;而如果换,那么你将赢得汽车。此时你赢得汽车的概率。所以,答案是:换门对你更好。

六、一百囚徒与一个灯泡(One Hundred Prisoners and a Light Bulb)

Van Ditmarsch教授详细讲解了这个谜题。

一百囚徒与一个灯泡谜题:100个囚徒,全部集中在监狱食堂,他们被告知会被送进独立关押室,然后在一个房间里逐个被审问,这个房里有一盏带开关的灯。囚徒之间可以通过开灯或关灯来相互交流(这是他们能够相互交流的唯一方式)。电灯最初是关着的。审问没有固定的次序或者审问间隔,同一个囚徒可以在任何阶段被再次审问。一个囚徒被审问时可以不做任何事情,也可以切换电灯开关,或者宣告所有囚徒都已被审问过了。如果这个宣告是真的,囚徒们都会被释放,但是如果它是假的,那么囚徒们都会被处决。当这些囚徒还在在食堂中,在被(永远)隔离之前,他们能达成一份协议使得他们被释放吗

Van Ditmarsch教授提供了思考这一逻辑谜题的思路。假设只有一名囚犯,那么协议很简单:如果一名囚犯进入审讯室,他就会宣布所有囚犯都已审问完毕。假设有两名囚犯,那么协议是:如果一名囚犯进入审讯室,而灯是关着的,他就把灯打开;如果一名囚犯进入审讯室时灯亮着,而他在之前的审讯中没有开灯,他就宣布所有囚犯都已接受审讯。

对于n名囚犯(n大于等于3)情形,指定其中一人作为计数器,不计数的囚犯为跟随者。跟随者遵循以下协议:第一次进入房间时,如果灯是关着的,他们就把灯打开;其他情况下,他们什么也不做。计数器则遵循不同的协议:当他进入审讯室时灯亮着,他就把灯关掉。当他第n  1次关灯时,他宣布每个人都已被审问。

假设每天进行一次审讯,需要28.5年时间囚徒才能出狱。这个时间可以减少到 9 年左右,其最小值未知。

七、八卦(Gossip)

八卦谜题说的是:有六个朋友,每个人都知道一个秘密。他们相互打电话,并且在每次通话中,他们相互交换他们所知道的全部秘密。问:需要多少次通话才能使每个人都知道所有秘密?

Van Ditmarsch教授首先给出了四个朋友的情形。假设a, b, c, d分别持有秘密A、B、C、D。此时只需四次通话:ab; cd; ac; bd. 也就是说,a和b先通话,这样a和b都有了AB这两个秘密;接着,c和d通话,这样c和d都有了CD两个秘密;然后,a和c通话,这样a和c知道了所有四个秘密;最后,b和d通话,以保证b和d也都知道所有四个秘密。

而对于六个朋友,比如a, b, c, d, e, f,分别持有A、B、C、D、E、F的情形,需要八次通话:ae; af; ab; cd; ac; bd; ae; af.

Van Ditmarsch教授指出该谜题在点对点通信、流行病学、语义网等领域中有诸多应用。

当然,这其中隐含了某个问题:c怎么知道他应该和d,而不是和a或b通话?为了解决这个问题,我们需要基于知识的八卦协议(knowledge-based gossip protocols)。

关于这些谜题,van Ditmarsch教授建议阅读One Hundred Prisonersand a Light Bulb这本书和它的中译本《一百囚犯与一个灯泡》以获得更详细的内容。同时,他也提供了网站以供查阅:http://personal.us.es/hvd/lightbulb.html

讲座最后,van Ditmarsch教授和现场师生围绕这七个谜题问题展开了激烈的讨论。讲座在热烈的掌声中圆满结束。

【图文/江丽莎】

【主讲人简介】

Hans van Ditmarsch 是法国国家科学研究中心的高级研究员。他在图卢兹的 lRlT 工作。此前,他曾在荷兰开放大学、格罗宁根大学、奥塔哥大学、阿伯丁大学、塞维利亚大学和法国国家科学研究中心(洛林大学/LORIA)工作。多年来,他还一直担任印度钦奈数学科学研究所的合作研究员。他在格罗宁根大学获得博士学位。他的研究领域包括知识和信念的动态变化、基于信息的安全协议、模态逻辑和组合学。他经常在 ESSLLl 暑期班授课,也是 LOFT、M4M、ESSLLl、逻辑教学工具(Tools for teaching logic) 和 LORI 等活动的组织者或主席。他还是《哲学逻辑杂志》(Journal of Philosophical Logic)的编辑。他是教科书和专著《动态认知逻辑》(Dynamic Epistemic Logic)的作者之一,《认知逻辑手册》(Handbook of Epistemic Logic)的编辑之一,以及逻辑谜题书《一百囚徒与一个灯泡》(One Hundred Prisoners and a Light Bulb)的作者之一。他曾获得欧洲研究理事会(ERC)的“认知协议综合”(Epistemic Protocol Synthesis)启动基金。