目前，我正在《新知客》杂志上主持一个趣题栏目。每月杂志发行后，我将在 Blog 上同步更新。点击 这里 可以查看往期题目。

推理
1. 在每一个小题中，我们都列出了八种物品，其中前面四种物品都有一个共同点，而这个共同点是后面四种物品所不具有的。请您找出这个共同点来。
(1) 小肠、地毯、水蜜桃、贵宾犬 | 牙刷、足球、藤椅、冰块
(2) 电线、棋子、指示灯、扇形图 | 闹钟、绳子、条形码、井字棋
(3) 电池、钥匙、酵母、书签 | 火柴、魔方、药瓶、订书机

2. 小 A 站在甲、乙两地之间的某个位置，他想乘坐出租车到乙地去。他看见一辆空车远远地从甲地驶来，而此时整条路上并没有别人与他争抢空车。我们假定车的行驶速度和人的步行速度都是固定不变的，并且车速大于人速。为了更快地到达目的地，小 A 应该怎样做呢？你认为下面哪种思路是正确的？
(A) 由于车速大于人速，小 A 应该尽可能早地上车，充分利用汽车的速度优势。因此，小 A 应该迎着空车走上去，提前与车相遇。
(B) 为了尽早到达目的地，小 A 应该充分利用时间，马不停蹄地赶往目的地。因此，他应该自己先朝目的地走一段路，再让出租车载他走完剩下的路程。

Read more…

在半径相等的半圆和圆中各画一个内接正方形。这两个正方形的面积之比是多大？有什么简单些的算法吗？
Read more…

    即使灯泡的初始状态不定，当 n=2 时，两个人也能保证都知道对方进过房间。假设双方手中各有两个球，囚犯 A 总是试图把自己的小球放进盒子，囚犯 B 总是试图把小球取走。如果 B 拿到了 4 个小球，他就知道了 A 一定来过房间；而只要 A 放好的小球被拿走了， A 也知道 B 进过了房间。
    但是，当 n>2 时，不存在这样的协议，使得有两个人都能获知所有人都已进过房间。 Peter Winkler 的 Mathematical Puzzles: A Connoisseur’s Collection 一书中给出了这个结论的一个大致证明思路。
    让我们考虑其中任何一个囚犯。我们假设他的策略是确定性的，他的下一步行动完全取决于之前看到的状态序列。假设在某一步，他看到的状态和上次离开房间时的状态相同，但他选择了改变状态。这时，你可以质问他，那你为啥不在上次就把状态改过来，偏偏要这次才去扳开关呢？看守完全有可能连续两次都是叫你进的房间，这样你不就浪费了一次进房间的机会了吗？因此，我们可以假设，当他进入房间时看见的状态和上次走的时候一样，他是不会去扳动开关的。
    接下来，让我们假设在某一步，这个囚犯的策略是“不动开关，保留原状态”。那么，我们可以认为他以后就再也不会动那个开关了！因为在最坏情况下，他根本没有改变灯泡状态的机会！具体地说，若无视掉这个囚犯以后的行动，今后的房间状态序列里必然有一种状态将出现无穷多次，比方说状态“开”出现了无穷多次吧。那么在最坏的情况下，这个囚犯从此开始总是在开灯的时候进屋。而他在这一步没有变动开关，并且以后的每一步里他所看到的状态都将和上次看到的一样，因此以后他都不会变动开关了。

Read more…

    说有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的。看守每次随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？

    这个经典的问题在网上转载无数，题目描述被好事者们改得天花乱坠，甚至加进了“这盏灯永远有充足的能源供应”、“如果灯泡坏了或是电路出了故障会马上修好”等条件，剥掉了“算法问题”的外壳，填补了本不存在的漏洞，让更多的人动起了脑筋。在论坛上，每次贴出这个问题，总会引起一大群人的口水战。但很不幸的是，这个题目的来源至今仍是个谜。据目前的已知情况推测，这个题目最早来源于 Berkeley 的电气工程荣誉学会，时间大概是 2001 年。在 2002 年的 7 月， IBM 的 Ponder This 趣题栏目介绍这个题目，囚犯与灯泡一炮走红，随即遍布网络的各个角落。 2003 年， The Mathematical Intelligencer 杂志上发表了一篇题为 One hundred prisoners and a lightbulb 的论文，也让囚犯们正式引起了数学家们的关注。

Read more…

    刚刚看到一道智力题，颇有些意思，说来给大家听听。我把题意稍微改了一下，原题中的 XX 侠是一个（不太容易解释的） lynch mob 。

    某座城市里发生了一起命案，已经确定凶手是 8 个嫌疑犯之一。经过很多可靠的调查，城南和城北的两名警探各自独立地把嫌疑犯的名单缩减到了两个人。现在，两名警探正在通电话，他们试图对比一下彼此的调查结果。如果他俩的嫌疑犯名单中正好只有一处重合，他们就能确定出凶手的身份了。但问题是，这座城市里有一个伸张正义、凌驾于法律之上的 XX 侠，他正在窃听两名警探的通话。如果他从中获知了凶手的身份，他将在警方实施拘捕之前先杀死凶手。
    现在， XX 侠已经知道了那 8 个嫌疑犯是谁，但不知道两名警探各自都把目标锁定在了哪两个人上。这两名警探之前从未见过面，这通电话是他们俩第一次进行交流。他们俩能成功地确定凶手的身份，而又不让 XX 侠知道凶手是谁吗？
    （当然，这里我们不允许使用那些基于数论的公钥加密体系，不然题目就没啥意思了）

Read more…