2024年11月8日下午15点，中国科学院大学人文学院2024年第21期“科学与人文”讲座在中国科学院哲学研究所报告厅举行。法国国家科学研究中心的Hans van Ditmarsch教授应邀开讲，讲座题为《一百囚徒与一个灯泡，及其他逻辑谜题》（One hundred prisoners and a light bulb-and other logic riddles）。中国科学院大学人文学院范杰副教授主持了本次讲座。
讲座伊始， 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)。
现在进行如下对话：
确定 (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）启动基金。
