Matrix67 |
2010-09-05 8:53 | 
即使灯泡的初始状态不定，当 n=2 时，两个人也能保证都知道对方进过房间。假设双方手中各有两个球，囚犯 A 总是试图把自己的小球放进盒子，囚犯 B 总是试图把小球取走。如果 B 拿到了 4 个小球，他就知道了 A 一定来过房间；而只要 A 放好的小球被拿走了， A 也知道 B 进过了房间。
但是，当 n>2 时，不存在这样的协议，使得有两个人都能获知所有人都已进过房间。 Peter Winkler 的 Mathematical Puzzles: A Connoisseur's Collection 一书中给出了这个结论的一个大致证明思路。
让我们考虑其中任何一个囚犯。我们假设他的策略是确定性的，他的下一步行动完全取决于之前看到的状态序列。假设在某一步，他看到的状态和上次离开房间时的状态相同，但他选择了改变状态。这时，你可以质问他，那你为啥不在上次就把状态改过来，偏偏要这次才去扳开关呢？看守完全有可能连续两次都是叫你进的房间，这样你不就浪费了一次进房间的机会了吗？因此，我们可以假设，当他进入房间时看见的状态和上次走的时候一样，他是不会去扳动开关的。
接下来，让我们假设在某一步，这个囚犯的策略是“不动开关，保留原状态”。那么，我们可以认为他以后就再也不会动那个开关了！因为在最坏情况下，他根本没有改变灯泡状态的机会！具体地说，若无视掉这个囚犯以后的行动，今后的房间状态序列里必然有一种状态将出现无穷多次，比方说状态“开”出现了无穷多次吧。那么在最坏的情况下，这个囚犯从此开始总是在开灯的时候进屋。而他在这一步没有变动开关，并且以后的每一步里他所看到的状态都将和上次看到的一样，因此以后他都不会变动开关了。
Sep
5
Sep
5
说有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的。看守每次随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？
这个经典的问题在网上转载无数，题目描述被好事者们改得天花乱坠，甚至加进了“这盏灯永远有充足的能源供应”、“如果灯泡坏了或是电路出了故障会马上修好”等条件，剥掉了“算法问题”的外壳，填补了本不存在的漏洞，让更多的人动起了脑筋。在论坛上，每次贴出这个问题，总会引起一大群人的口水战。但很不幸的是，这个题目的来源至今仍是个谜。据目前的已知情况推测，这个题目最早来源于 Berkeley 的电气工程荣誉学会，时间大概是 2001 年。在 2002 年的 7 月， IBM 的 Ponder This 趣题栏目介绍这个题目，囚犯与灯泡一炮走红，随即遍布网络的各个角落。 2003 年， The Mathematical Intelligencer 杂志上发表了一篇题为 One hundred prisoners and a lightbulb 的论文，也让囚犯们正式引起了数学家们的关注。
Sep
3
刚刚看到一道智力题，颇有些意思，说来给大家听听。我把题意稍微改了一下，原题中的 XX 侠是一个（不太容易解释的） lynch mob 。
某座城市里发生了一起命案，已经确定凶手是 8 个嫌疑犯之一。经过很多可靠的调查，城南和城北的两名警探各自独立地把嫌疑犯的名单缩减到了两个人。现在，两名警探正在通电话，他们试图对比一下彼此的调查结果。如果他俩的嫌疑犯名单中正好只有一处重合，他们就能确定出凶手的身份了。但问题是，这座城市里有一个伸张正义、凌驾于法律之上的 XX 侠，他正在窃听两名警探的通话。如果他从中获知了凶手的身份，他将在警方实施拘捕之前先杀死凶手。
现在， XX 侠已经知道了那 8 个嫌疑犯是谁，但不知道两名警探各自都把目标锁定在了哪两个人上。这两名警探之前从未见过面，这通电话是他们俩第一次进行交流。他们俩能成功地确定凶手的身份，而又不让 XX 侠知道凶手是谁吗？
（当然，这里我们不允许使用那些基于数论的公钥加密体系，不然题目就没啥意思了）
Aug
28
和大家分享一张超级帅的 T 恤印花，数学各个分支领域中最深刻最神奇的结论在此汇聚一堂，组成了一个心形。
你能从中认出多少个经典的数学研究对象和结论？
Aug
23
经典 Geek 动画 Futurama 上周播出了第 6 季的第 10 集 The Prisoner of Benda 。在这一集中，教授 Farnsworth 发明了一种“心灵对换机”，它可以把两个人的思想互相对换，使得 A 的大脑跑进 B 的身体里，而 B 的大脑则跑到 A 的身体里。 Farnsworth 和 Amy 都想得到对方的身体，便成为了这台机器的第一对实验者。等到他们爽够了想换回来后， Farnsworth 却发现了一个严重的问题：已经互换过大脑的两个身体不能再次进行大脑对换操作。但这并不表示两个人完全没有希望回到自己的身体里—— Farnsworth 突然想到，或许可以用第三者作为一个临时的大脑储存空间，从而实现间接对换。正巧机器人 Bender 进了实验室，于是（身为 Amy 的） Farnsworth 和 Bender 又坐上了机器，这下 Farnsworth 的大脑便跑到 Bender 身体里了，而 Bender 的大脑则进了 Amy 的身体里。此时 Farnsworth 才意识到，引入一个第三者是不够的——再让（身为 Bender 的） Farnsworth 和（身为 Farnsworth 的） Amy 互换大脑，可以让 Farnsworth 恢复原状，但同时 Amy 的大脑会跑到 Bender 的身体里去；这样 Bender 和 Amy 的身体正好颠倒了，而他们却已不能再次使用机器。换句话说，要想恢复两个换位了的大脑，需要引入不止一个新的人。
但现在，问题已经变得更加复杂了——这下已经产生了三个大脑位置错乱的人。大家很容易联想到一个更一般的问题：给定 n 个人以及他们之前使用“心灵对换机”的记录，至少得引入多少个新的人，才能让所有人的大脑都“物归原主”呢？
Aug
16
目前，我正在《新知客》杂志上主持一个趣题栏目。每月杂志发行后，我将在 Blog 上同步更新。点击 这里 可以查看往期题目。
推理
1. 下一个图形是什么？
2. 小 A 和小 B 玩游戏。小 A 取出一副扑克牌并去掉大小王，剩下红色的牌和黑色的牌各 26 张。洗好牌后，小 A 依次翻开每一张牌，让小 B 看到牌的颜色。小 B 可以在任意时刻打断小 A ，并打赌“下一张牌是红色”。如果下一张牌真是红色，小 A 给小 B 一块钱；如果下一张牌是黑色的，小 B 输给小 A 一块钱。注意，小 B 必须要在某个时刻下赌注，并且机会只有一次；如果他一直没打断小 A ，则默认他赌最后一张牌是红色。
小 B 的最佳策略是什么？在这种策略下，他有多大的概率获胜？
