经典智力题高频题库

题面

有 1000 瓶外观完全相同的酒，其中恰好 1 瓶有毒。毒发时间固定为 24 小时：只要老鼠喝到那瓶毒酒的样本，24 小时后一定死亡；没有喝到毒酒就一定存活。

你只有一次测试窗口。也就是说，所有喂食安排都必须现在一次性设计好，不能等看到部分结果后再补测。每只老鼠可以喝很多瓶酒各取一小滴混在一起的样本。

24 小时后，你只能看到每只老鼠是死还是活。要求无论哪一瓶有毒，都能根据这组死活结果唯一指出毒酒。问最少需要几只老鼠。

第一原则

一只老鼠本质上是在回答一个是或否的问题：毒酒是否在我喝过的那一组瓶子里？m 只老鼠最后最多给出 $2^m$ 种死活模式。要从 1000 个可能答案中保证选出 1 个，模式数至少要覆盖 1000；9 只老鼠只有 512 种，不够，10 只老鼠有 1024 种，才有可能。接下来只要把每瓶酒分配到一个唯一的 10 位编码即可。

详细解法

1. 先证明下限：如果只有 9 只老鼠，最终只有 $2^9=512$ 种死活模式，但毒酒可能是 1000 瓶中的任意一瓶。至少有两个瓶号会落到同一种模式里，所以 9 只无法保证区分。
2. 再证明 10 只够用：把 1000 瓶酒编号为 0 到 999。10 位二进制一共有 $2^10=1024$ 个标签，足够给每瓶酒分配一个互不相同的标签。
3. 把每个瓶号写成 10 位二进制，不足 10 位就在左边补 0。例如 613 号瓶写成 1001100101，因为 $613=512+64+32+4+1$。
4. 让第 i 只老鼠负责第 i 个二进制位：凡是这一位为 1 的瓶子，都取一滴给这只老鼠喝；这一位为 0 的瓶子，就不给这只老鼠喝。
5. 为什么这样能解码？因为只有 1 瓶有毒。第 i 只老鼠会死，恰好说明毒酒瓶号的第 i 位是 1；第 i 只老鼠活着，恰好说明那一位是 0。
6. 24 小时后，把死记为 1，把活记为 0，按老鼠对应的位顺序排成 10 位二进制数。这个数对应的编号，就是唯一可能的毒酒编号。
7. 所以 9 只老鼠不够，10 只老鼠有明确构造，最少数量就是 10 只。

题面

有四个人在夜里要从左岸过到右岸。他们各自单独过桥所需时间分别是 1、2、5、10 分钟。桥很窄，每次最多只能有两个人在桥上，也可以只有一个人过桥。

桥上没有灯，唯一的光源是一支火把。任何一次过桥或返回，都必须有人亲手带着火把；火把不能扔过去，不能隔空传递，也不能自己回来。

如果两个人一起走，速度由较慢的人决定。例如 5 分钟的人和 10 分钟的人一起过桥，这次耗时是 10 分钟，而不是 15 分钟。

开始时四个人和火把都在左岸。目标是让四个人最终都在右岸，并且总耗时尽可能短。问最少需要多少分钟。

第一原则

这题的核心不是“谁最快就让谁一直跑”，而是先看必须付出的成本。10 分钟的人一定要过桥一次，5 分钟的人也一定要过桥一次；同时，火把还必须被带回来给左岸剩下的人使用。因为返回也要花时间，最优安排要同时考虑“谁把最慢两人送过去”和“谁把火把带回来”。对四个人 $a\le b\le c\le d$ 来说，只需要比较两种有竞争力的模板：让 c 和 d 一起过，或让最快的 a 分别护送 c、d 过。

详细解法

1. 先把四个人按时间从快到慢记为 a、b、c、d。本题中 $a=1$，$b=2$，$c=5$，$d=10$。
2. 最慢的 c 和 d 迟早都要到右岸。它们如果分开过，就至少要分别付出 c 和 d 的时间；它们如果一起过，只需要付出 d 的时间，因为两人同行按较慢者计时。
3. 但是 c 和 d 一起过桥之前，右岸必须有人能把火把带回来，否则左岸剩下的人无法继续行动。最便宜的返回者应该从最快的 a 和 b 中选择，而不是让 5 或 10 分钟的人回来。
4. 第一种模板是“两个最快的人做接力”：$a+b$ 先过，a 回来，$c+d$ 一起过，b 回来。这样 c 和 d 已经在右岸，火把又回到左岸，成本是 $b+a+d+b$，也就是 $a+2b+d$。
5. 第二种模板是“最快的人 a 来回护送”：$a+d$ 过，a 回来，$a+c$ 过，a 回来。这样 c 和 d 也在右岸，火把也回到左岸，成本是 $d+a+c+a$，也就是 $2a+c+d$。
6. 代入 1、2、5、10：第一种模板成本是 $2+1+10+2=15$；第二种模板成本是 $10+1+5+1=17$。先处理最慢两人时，第一种更省。
7. 执行第一种模板后，左岸只剩 1 和 2，并且火把在左岸。最后让 1 和 2 一起过桥，耗时 2 分钟。
8. 完整时间线是：1 和 2 过桥用 2 分钟，1 返回用 1 分钟，5 和 10 过桥用 10 分钟，2 返回用 2 分钟，1 和 2 再过桥用 2 分钟。总计 $2+1+10+2+2=17$ 分钟。
9. 为什么这已经是最优？四个人至少需要三次向右过桥和两次带火把返回；最慢两人要么一起过，要么分开过。上面两种模板正好覆盖这两种有竞争力的情况，并且每次返回都选最快可用的人，所以没有更低成本的安排。

题面

100 名囚犯被关在彼此隔离的牢房里。每天，狱卒随机挑选其中 1 人进入一间特殊房间。房间里只有一盏灯，灯只有亮和灭两种状态；本版本约定开始时灯是灭的。

进入房间的人可以看见灯当前是亮还是灭，也可以选择把灯打开、关掉，或者什么都不做。离开房间后，他不能告诉别人自己看见了什么，也不能留下纸条、划痕等其他记号。

所有囚犯只允许在游戏开始前共同商量一套策略。游戏开始后，他们被随机叫进房间，顺序不可预测，同一个人可能连续被叫到，某些人也可能很久都没有机会。

任意一名囚犯在自己进房时都可以宣布：“所有 100 人都至少进过这间房一次。”如果宣布正确，100 人全员获救；如果宣布错误，策略失败。目标是在公平的随机访问会长期给每个人机会的前提下，最终能正确宣布，并且绝不误报。

第一原则

第一性原理是：灯泡本身只能存 1 个比特，也就是“亮/灭”这一个可见状态。它记不住是谁来过，也记不住来过多少人，所以不能让大家随便开关。可靠做法是把灯当成一只一次只能装一封信的信箱：非计数员只负责投递“我来过”这封信一次，计数员只负责取信并计数。随机访问只会影响取信和投信等待多久，不会改变“每封信最多来自一个新人、每封信最终会被计数员取走”的逻辑。

详细解法

1. 先选定 1 人做计数员，例如 P0。计数员自己一开始就知道“我本人已经至少进过一次”的时刻：只要 P0 第一次被叫进房间，他就满足这一点。因此他需要确认的只剩另外 99 人。
2. 其余 99 人都是发送者。每个发送者心里只保存一个私人状态：我有没有发送过自己的信号。开始时每个人都记为“未发送”。
3. 发送者的规则很简单：如果他还未发送，并且这次进房看到灯是灭的，就把灯打开，然后把自己记为“已发送”。如果灯已经亮着，说明信箱里已有别人的信，他不能覆盖；如果自己已经发送过，以后无论看到什么都不再开灯。
4. 计数员的规则也很简单：每次进房如果看到灯亮，就把灯关掉，并把自己的计数加 1；如果看到灯灭，就什么都不做。
5. 为什么计数不会重复？因为一个发送者一生只会把灯从灭改成亮一次。计数员每次看到亮灯，只能说明有某个尚未发送过的人在他上次关灯之后投递了一次信号。
6. 为什么计数不会漏掉已经发送的信号？因为灯一旦被某个发送者打开，就会一直亮着，直到计数员来把它关掉。其他人看到亮灯也不动它，所以这封信不会被擦掉或混淆。
7. 当计数员数到 99 时，已经收到 99 个互不重复的发送者信号。发送信号的前提是那个人本人进过房间，所以另外 99 人都来过；计数员本人当然也来过，因为宣布发生在他某次进房时。因此这时宣布一定正确。
8. 随机访问为什么不破坏可靠性？随机顺序可能让灯长时间亮着、也可能让某个新人很晚才遇到灭灯，但它不会制造假信号。在每天独立随机选择的经典模型下，每个人会一再获得机会的概率为 1；计数员也会反复回来清空信箱。因此等待时间不可预知，但最终收满 99 个信号的概率为 1。

题面

桌上共有 3 顶黑帽、2 顶白帽。主持人给 A、B、C 三个人各戴一顶帽子，剩下两顶收起来。每个人都能看见另外两个人的帽子颜色，但永远看不见自己的帽子颜色。

所有人都知道这些规则：黑帽总共 3 顶，白帽总共 2 顶；每个人都只会在能够确定时才回答；大家都足够理性；并且大家也知道别人同样知道这些规则。这种“所有人都知道，且知道别人也知道”的条件叫公共知识。

主持人一轮一轮地问：现在有谁能确定自己帽子的颜色？如果没人回答，就进入下一轮。经典情形是 A、B、C 实际都戴黑帽。为什么他们只凭别人的帽子和连续沉默，最后都能确定自己是黑帽？

第一原则

这题的关键不是“我看见了什么”，而是“如果某种情况是真的，别人此刻应该会看见什么、知道什么、说什么”。每一轮沉默都会变成所有人共同听到的新信息，从而排除一批可能情况。

详细解法

1. 先从最简单的情况想起：如果某人看到另外两人都是白帽，他会立刻知道自己是黑帽。理由很朴素：白帽总共只有 2 顶，已经都在别人头上了，自己的帽子不可能再是白帽。
2. 第一轮没人回答，因此所有人都同时知道：没有任何人看见“两顶白帽”。如果真的有两个人戴白帽，第三个戴黑帽的人就会看见两白并立刻回答。既然没有人回答，“两人戴白”的情况被排除。
3. 接着看“一人戴白”的假设。假设 A 是白帽，B、C 是黑帽。那么 B 会看见 A 白、C 黑。B 会想：如果我也是白帽，C 就会看见两顶白帽，C 第一轮就该回答；但第一轮 C 没回答，所以我不是白帽，我是黑帽。C 也会做同样推理。
4. 所以在“一人戴白”的世界里，两个黑帽人会在第二轮知道自己是黑帽并回答。换句话说，第二轮如果仍然没人回答，就说明“一人戴白”的情况也不可能。
5. 真实情形中 A、B、C 都看见另外两人是黑帽。第一轮沉默后，他们只排除了“两白”；第二轮沉默后，他们又排除了“一白”。剩下唯一可能就是“三人全黑”，所以第三轮三个人可以同时回答：我是黑帽。
6. 这个推理依赖公共知识：不只是 A 知道 B 理性，还要 A 知道 B 会用第一轮沉默推理，B 也知道 A 会这样想。沉默之所以有力量，正是因为每个人都能把同一段沉默当成共同证据。

题面

三扇关闭的门后面放着一辆车和两只羊。车的位置是随机的；你不知道车在哪，只能先选一扇门。

主持人知道每扇门后面是什么。他必须打开一扇你没有选的门，而且这扇门后面一定是羊，不能打开车，也不能打开你选的门。

主持人打开一扇羊门后，场上还剩两扇没开的门：你原来选的门，以及另一扇门。主持人总会给你一次机会：坚持原选择，还是换到另一扇门。

在这些规则都成立时，你应该换门吗？坚持不换和选择换门，各自赢车的概率是多少？

第一原则

第一次选择已经把概率分成两块：你选中的那扇门有 $\frac{1}{3}$ 概率有车，另外两扇门合起来有 $\frac{2}{3}$ 概率有车。主持人知道答案，并且必定从“另外两扇门”里排除一扇羊门，所以那 $\frac{2}{3}$ 不会平均消失，而是转移到剩下那扇未开的门上。

详细解法

1. 先看第一次选择。三扇门只有一扇有车，所以第一次就选中车的概率是 $\frac{1}{3}$；第一次选到羊的概率是 $\frac{2}{3}$。
2. 如果你第一次选中车，主持人只能从另外两扇羊门里打开一扇。此时你若换门，就会从车换到羊，所以换门会输。
3. 如果你第一次选到羊，另外两扇门里必定是一辆车和一只羊。主持人不能开车，也不能开你的门，所以他只能打开那只羊。
4. 在第一次选到羊的情况下，主持人打开羊门后，剩下那扇未打开、且不是你原选择的门必定是车，所以换门一定赢。
5. 因此，“换门赢”与“第一次选错”是同一件事，概率是 $\frac{2}{3}$。
6. “不换赢”只发生在第一次就选中车的时候，概率是 $\frac{1}{3}$。
7. 看起来开门后只剩两扇门，但这两扇门不是重新随机洗牌出来的；其中一扇保留了你最初选择的 $\frac{1}{3}$，另一扇承接了最初未选区域的 $\frac{2}{3}$。

题面

有 12 个外观完全相同的球，其中恰好 1 个球重量异常。其他 11 个球重量完全相同；异常球可能比正常球重，也可能比正常球轻，开始时你不知道是哪一种。

你只有一架左右天平。每次称重时，可以在左盘和右盘各放同样数量的球，天平只会给出三种结果之一：左盘重、右盘重、平衡。它不会告诉你具体重了多少。

最多只能称 3 次。每一次称什么，可以根据前面已经看到的结果来决定。最后必须同时回答两个问题：哪一个球异常，以及它是偏重还是偏轻。

第一原则

一个“可能答案”不是单独的球号，而是“某球偏重”或“某球偏轻”。12 个球共有 24 种可能答案。一次天平称重像一个三选一问题：结果可能是左重、右重、平衡；三次最多形成 $3^3=27$ 条结果路径，所以信息容量够用。但 $3^3\ge 24$ 只说明“叶子数量可能够”，还没有给出称法。真正要做的是构造一棵决策树：每次称重都把当前候选的“球号+方向”尽量分成三组，并保证走到第三次后，每一种结果都能对应唯一答案。

详细解法

1. 先给 12 个球编号为 1 到 12。第一次称 1、2、3、4 对 5、6、7、8。
2. 如果第一次平衡，说明 1 到 8 全部正常，异常球只可能在 9、10、11、12 中。第二次称 9、10、11 对 1、2、3，其中 1、2、3 已经是正常参照。
3. 在平衡分支里，如果第二次也平衡，异常球就是 12。第三次称 12 对 1：12 重就是 12 偏重，12 轻就是 12 偏轻。
4. 在平衡分支里，如果第二次左重，异常球只能是 9、10、11 中的某一个偏重。第三次称 9 对 10：哪边重就是哪个球偏重；若平衡，就是 11 偏重。
5. 在平衡分支里，如果第二次右重，异常球只能是 9、10、11 中的某一个偏轻。第三次称 9 对 10：哪边轻就是哪个球偏轻；若平衡，就是 11 偏轻。
6. 如果第一次左重，不能说 1 到 4 都“可疑为重”这么简单；准确候选是 1 重、2 重、3 重、4 重、5 轻、6 轻、7 轻、8 轻。此时 9 到 12 都是正常球。
7. 第一次左重时，第二次称 1、2、5 对 3、6、9。若第二次左重，候选只剩 1 重、2 重、6 轻；第三次称 1 对 2，哪边重就是哪个球偏重，若平衡就是 6 偏轻。
8. 第一次左重时，若第二次右重，候选只剩 3 重、5 轻；第三次称 3 对 9，若 3 比正常球重就是 3 偏重，若平衡就是 5 偏轻。
9. 第一次左重时，若第二次平衡，候选只剩 4 重、7 轻、8 轻；第三次称 7 对 8，若平衡就是 4 偏重，哪边轻就是哪个球偏轻。
10. 如果第一次右重，做同一套交叉称重，方向全部镜像：第二次仍称 1、2、5 对 3、6、9。
11. 第一次右重时，若第二次右重，候选是 1 轻、2 轻、6 重；第三次称 1 对 2，哪边轻就是哪个球偏轻，若平衡就是 6 偏重。
12. 第一次右重时，若第二次左重，候选是 3 轻、5 重；第三次称 3 对 9，若 3 比正常球轻就是 3 偏轻，若平衡就是 5 偏重。
13. 第一次右重时，若第二次平衡，候选是 4 轻、7 重、8 重；第三次称 7 对 8，若平衡就是 4 偏轻，哪边重就是哪个球偏重。
14. 至此，第一次的三种结果、第二次的三种结果、第三次的判定都被覆盖。每条真实路径最后只留下一个“球号+偏重/偏轻”答案，所以三次称重足够。

题面

有一栋 100 层楼，楼层编号为 1 到 100。你有 2 枚完全相同的鸡蛋，可以从任意楼层往下扔。

存在一个未知的最高安全楼层 F。只要从 F 层或更低楼层扔，鸡蛋一定不会碎；只要从 $F+1$ 层或更高楼层扔，鸡蛋一定会碎。F 可能是 0，表示 1 楼也会碎；F 也可能是 100，表示 100 楼也安全。

鸡蛋碎了就不能再用；没有碎的鸡蛋可以继续使用。每次扔完之后，你都可以根据碎或没碎的结果决定下一次扔哪一层。

目标不是碰巧很快找到答案，而是设计一种保证策略：无论真实的 F 是多少，都能确定 F。问在最坏情况下，最少需要扔多少次。

第一原则

这题的关键资源不是楼层，而是鸡蛋。用普通二分时，如果第一枚蛋在 50 楼碎了，剩下 1 枚蛋就不能再跳着试 25 楼、37 楼，因为它再碎就没有信息来源了；只能从 1 楼往上逐层查，最坏会把总次数拖到 50 次。两枚鸡蛋的最优策略要先选一个最坏次数上限 x，然后让每一次“当前一扔 + 碎后逐层回查”都刚好不超过 x。第一次最多跳 x 层，第二次最多再跳 $x-1$ 层，第三次最多再跳 $x-2$ 层，于是覆盖能力是 $x+(x-1)+\ldots +1$。

详细解法

1. 先理解只有 1 枚鸡蛋时会发生什么。假设你已经知道 L 层安全、U 层会碎，而答案 F 在 L 到 U 之间。只剩 1 枚蛋时，不能跳过中间楼层；如果直接从较高楼层扔且碎了，被跳过的楼层就再也无法区分。因此只能从 $L+1$、$L+2$、$L+3$ 这样逐层往上试。
2. 所以第一枚蛋的作用，是把 100 层切成若干小段。一旦第一枚蛋在某一站碎了，第二枚蛋就在上一站和这一站之间逐层查完。
3. 为什么不是二分？二分的第一步会试 50 楼。如果 50 楼碎了，只剩 1 枚蛋，要区分 $F=0$、1、2、...、49，只能从 1 楼逐层试到 49 楼。最坏总次数是 $1+49=50$ 次，远远不是最优。
4. 现在假设我们希望最坏不超过 x 次。第一次如果从第 x 层扔并且碎了，下面最多有 $x-1$ 层需要用第二枚蛋逐层查，总次数正好不超过 x。
5. 如果第 x 层没碎，已经用掉 1 次，还剩 $x-1$ 次。下一跳就不能再跳 x 层，只能跳 $x-1$ 层；否则第二次碎了以后，中间楼层会多到查不完。
6. 同理，第三跳最多再上 $x-2$ 层，第四跳最多再上 $x-3$ 层。每安全一次，剩余次数少 1，所以下一段长度也必须少 1。
7. 因此 x 次最多能覆盖 $x+(x-1)+(x-2)+\ldots +1$ 层，也就是 $x(x+1)/2$ 层。这个式子不是公式魔法，而是在数每一次第一枚蛋碎掉时，第二枚蛋还能线性回查的最大段长。
8. 比较 100 层需要的最小 x：13 次最多覆盖 $13\times \frac{14}{2}=91$ 层，不够；14 次最多覆盖 $14\times \frac{15}{2}=105$ 层，足够覆盖 100 层。
9. 实际策略是从 14 楼开始，然后按递减间隔走：14、27、39、50、60、69、77、84、90、95、99、100。只要第一枚蛋在某一站碎了，就用第二枚蛋从上一站的下一层开始逐层试。
10. 例如 27 楼碎了，就已经知道 14 楼安全、27 楼会碎，只需查 15 到 26 共 12 层。此时已经扔了 2 次，还剩 12 次，刚好够。
11. 无论第一枚蛋在哪一站碎，还是一路到 100 楼都不碎，总次数都不会超过 14。又因为 13 次最多只能覆盖 91 层，所以最坏情况最少就是 14 次。

题面

5 名海盗要分 100 枚金币。按资历从高到低编号为 A、B、C、D、E，A 最老，E 最年轻。金币不能切开，每个人拿到的数量必须是整数。

每一轮都由当前还活着、资历最高的海盗提出分配方案，然后所有活着的海盗一起投票，提案者本人也投票。

若赞成票达到活着人数的一半或以上，方案立刻通过；否则提案者被扔下海，下一位资历最高的海盗继续提案。

所有海盗完全理性，比较顺序是：先保命，再尽量多拿金币；如果自己是否活着和金币数都一样，就倾向于让当前提案者死。问 A 第一轮应怎样分，才能让自己拿到最多金币并通过投票。

第一原则

这是逆向归纳：不要先猜 5 人局，而是从最后只剩 1 人时的确定结果开始，逐层往前推。n 人局的通过门槛是 $ceil(\frac{n}{2})$ 票，也就是人数的一半向上取整，且提案者会投自己赞成票；其他人只会比较“接受当前方案能拿多少”和“让提案者死后下一轮自己能拿多少”。因为平局时会让提案者死，所以收买一票必须给对方严格多于下一轮收益。

详细解法

1. 先算投票门槛。2 人局需要 1 票，3 人局需要 2 票，4 人局需要 2 票，5 人局需要 3 票。这里的票数包含提案者自己的赞成票。
2. 1 人局只剩 E，没有投票博弈，E 会拿走全部 100 枚金币。
3. 2 人局是 D、E。门槛是 1 票，D 自己赞成就够，因此 D 可以提 D100、E0。E 反对也无法阻止方案通过。
4. 3 人局是 C、D、E。C 需要 2 票，自己已有 1 票，还要再买 1 票。若 C 死，下一轮 D 会拿 100，E 会拿 0；所以 D 已经不可能拿得更多，E 只要拿到 1 就比下一轮的 0 好。C 提 C99、D0、E1。
5. 4 人局是 B、C、D、E。B 需要 2 票，自己已有 1 票，还要再买 1 票。若 B 死，上一段告诉我们 C99、D0、E1；D 的下一轮收益是 0，所以给 D 1 枚就能让 D 赞成。B 提 B99、C0、D1、E0。
6. 5 人局是 A、B、C、D、E。A 需要 3 票，自己已有 1 票，还要再买 2 票。若 A 死，下一轮是 B99、C0、D1、E0。
7. 因此 C 和 E 的拒绝价最低：他们下一轮都是 0，各给 1 就会赞成。D 下一轮能拿 1，必须给 2 才会赞成；B 下一轮能拿 99，必须给 100 才会赞成，而 A 还需要另一票。A 当然选最便宜的 C 和 E。
8. 最终 A 提 A98、B0、C1、D0、E1。A 自己赞成，C 和 E 因为 $1>0$ 也赞成，正好 3 票达到 5 人局门槛，方案通过。

题面

桌上有两根可以燃烧的绳子。每根绳子从任意一端单独点燃，从点火到完全烧完都正好需要 60 分钟。

绳子的粗细、材料或湿度可能沿途不同，所以燃烧速度不均匀。某一半长度可能烧 5 分钟，另一半长度可能烧 55 分钟；题目没有给你任何刻度或均匀性。

你有足够的火柴，可以在任意时刻点燃任意一根绳子的任意一端。绳子一旦烧完就会完全消失，不能重复使用。

在不能量长度、不能剪绳子、不能假设中点的前提下，怎样精确量出 45 分钟？

第一原则

这题的关键不是“长度”，而是“剩余单端燃烧时间”。一根绳子从一端单独烧完需要 60 分钟，说明整根绳子含有 60 分钟的可燃时间量。速度不均匀只会影响火焰在真实长度上的位置，不会改变整根的总时间量。两端同时点燃时，左端火焰每过 1 分钟吃掉 1 分钟的单端时间量，右端火焰也每过 1 分钟吃掉 1 分钟的单端时间量；两个火焰合起来每分钟消耗 2 分钟的时间量，所以 60 分钟的总量会在 30 分钟内消耗完。

详细解法

1. 把两根绳子分别叫 A 和 B。开始计时时，同时点燃 A 的两端，并点燃 B 的一端。
2. 先看 A。A 原本从单端烧完要 60 分钟。现在它的两端都在烧，两个火头共同消耗这 60 分钟的时间量，因此 A 会在 30 分钟后烧完。这里不需要知道火头在绳子上的物理位置。
3. A 烧完的瞬间，就是从开始起过去了 30 分钟。此时 B 只从一端烧了 30 分钟。因为 B 单端总共要 60 分钟，所以如果让它继续只从这一端烧，还需要 30 分钟才能烧完。
4. 立刻点燃 B 的另一端。现在 B 剩下的不是“半根长度”，而是“30 分钟的单端燃烧时间量”。两端一起烧会以两倍速度消耗这段剩余时间量。
5. 所以 B 剩下的 30 分钟时间量会在 15 分钟内烧完。开始后的 30 分钟加上这 15 分钟，正好是 45 分钟。
6. 因此做法是：A 两端点、B 一端点；A 烧完时点燃 B 的另一端；B 烧完时停止计时。

题面

你有两个空桶：一个最多装 3 升，一个最多装 5 升。两个桶都没有刻度，所以你看不出“半桶”“大约 4 升”这样的中间水量。

水源无限。每一步只允许三种可靠操作：把某个桶装满，把某个桶倒空，或者把一个桶倒进另一个桶，直到倒水的桶空了，或接水的桶满了。

目标是得到精确的 4 升水。因为 3 升桶装不下 4 升，所以最后这 4 升必须留在 5 升桶里。问怎样操作，并说明为什么每一步的水量都是确定的。

第一原则

没有刻度时，精确性来自“边界”，不是来自眼力。装满能得到 3 或 5，倒空能得到 0，从一个桶倒到另一个桶会停在两个可靠边界之一：源桶空，或目标桶满。把状态写成 (3 升桶水量, 5 升桶水量)，每次合法操作都会把一个确定状态变成另一个确定状态。这个题的关键是先用 $5-3$ 得到精确的 2 升，再把这 2 升放进 3 升桶，使 3 升桶只剩 1 升空间；随后满的 5 升桶只需要倒出这 1 升，就必然留下 4 升。

详细解法

1. 先约定状态写法：(x,y) 表示 3 升桶里有 x 升，5 升桶里有 y 升。开始两个桶都是空的，所以状态是 (0,0)。
2. 把 5 升桶装满，状态从 (0,0) 变成 (0,5)。这一步可靠，因为“装满 5 升桶”直接给出精确 5 升。
3. 把 5 升桶倒入 3 升桶，直到 3 升桶满。3 升桶从 0 到 3，需要接走 3 升，所以 5 升桶从 5 剩到 2，状态变成 (3,2)。
4. 把 3 升桶倒空，状态变成 (0,2)。注意这一步保留了 5 升桶里的 2 升，不要把 5 升桶倒掉。
5. 把 5 升桶里的 2 升倒进 3 升桶，状态变成 (2,0)。现在 3 升桶里精确有 2 升，因此它距离装满还差 1 升。
6. 再次把 5 升桶装满，状态变成 (2,5)。此时 5 升桶有 5 升，3 升桶只缺 1 升。
7. 把 5 升桶倒入 3 升桶，直到 3 升桶满。因为 3 升桶只差 1 升，所以这次只能从 5 升桶倒出 1 升；5 升桶从 5 减到 4，最终状态是 (3,4)。
8. 最后的 4 升为什么留在 5 升桶里？因为这一步的停止条件是“3 升桶满”，而 3 升桶在倒水前只缺 1 升。倒水一旦补满这 1 升就必须停止，所以满的 5 升桶只失去 1 升，剩下的 $5-1=4$ 升仍在 5 升桶中。

题面

房间外并排有 3 个开关，记为 A、B、C。房间里面只有 1 盏灯，而且 3 个开关中恰好只有 1 个开关控制这盏灯。

门关着的时候，你完全看不到房间里的灯。你可以站在门外随意拨动开关，也可以等待一段时间；但一旦打开门进房间，就不能再回到门外继续试开关，也不能再拨动开关。

灯一开始是灭的。题目默认这是一只传统灯泡：它亮过一段时间后会变热，关掉后也会在短时间内保留余热，并且你进屋时可以安全地摸到或感受到它的温度。

问题是：只进房间一次，怎样确定 A、B、C 中到底哪一个开关控制这盏灯？

第一原则

如果只看灯现在亮不亮，一次进门只能分出两种结果：亮或灭，不够区分三个开关。关键是把时间也用起来：让某个开关提前打开一段时间，灯泡如果真的被它控制，就会把“刚才亮过”记录成热量。这样进门时能读到三种状态：正在亮、灭但热、灭且冷。亮表示当前被打开的开关有效；灭但热表示先前打开过又关掉的开关有效；灭且冷表示前两个都无效，只能是剩下的开关。

详细解法

1. 先把三个开关命名为 A、B、C。名字本身不重要，只是为了让步骤说得清楚。
2. 打开开关 A，等待几分钟。等待的作用不是为了观察，因为你还在门外看不到灯；它的作用是让灯泡在 A 真正控制它时积累热量。
3. 等待后，把 A 关掉。此时如果 A 是正确开关，灯已经不亮了，但灯泡还会留下余热；如果 A 不是正确开关，灯泡从头到尾没有被 A 点亮，也不会因为 A 变热。
4. 接着打开开关 B，并且立刻进房间。这里要“立刻”，因为 B 的信息是当前状态：如果 B 控制灯，进门时灯应该正在亮。
5. 进屋后先看灯是否亮。灯亮，说明当前打开的 B 正在给灯供电，所以控制开关是 B。
6. 如果灯不亮，再判断灯泡是否热。灯灭但热，说明它刚才亮过，现在又被关掉了；这正好对应“先打开、后关掉”的 A，所以控制开关是 A。
7. 如果灯不亮而且灯泡是冷的，说明 A 没有让它亮过，B 也没有让它现在亮起来。题目说三者中恰好有一个控制灯，因此剩下的 C 就是答案。
8. 这道题的本质是给三个开关安排三种可区分的观察结果：A 对应“过去亮过，留下热”；B 对应“现在正在亮”；C 对应“过去没亮，现在也没亮”。一次进门不是只读一个亮灭信号，而是同时读当前亮灭和过去热量两个线索。

题面

走廊上有 100 扇门，编号为 1 到 100。开始时，每一扇门都是关着的。

接下来做 100 轮操作。第 1 轮切换每一扇门；第 2 轮只切换编号是 2 的倍数的门；第 3 轮只切换编号是 3 的倍数的门；一直这样继续。

这里的“切换”意思是：原来关着就打开，原来开着就关上。第 k 轮会切换所有编号能被 k 整除的门，也就是 k、2k、3k、... 这些门。

完成第 100 轮之后，哪些编号的门仍然开着？请不要只给模拟结果，还要说明为什么这些门一定开着、其他门一定关着。

第一原则

一扇门的最终状态只取决于它被切换了奇数次还是偶数次。编号为 n 的门，会在第 k 轮被切换，当且仅当 k 是 n 的约数。因此问题变成：哪些数有奇数个约数？约数通常按 $a\times b=n$ 成对出现，只有完全平方数会多出一个无法配成两份的平方根约数，所以只有完全平方数有奇数个约数。

详细解法

1. 先只看一扇门，例如 n 号门。它什么时候会被碰到？第 k 轮切换 k 的倍数门，所以 n 号门会被切换，正好等价于 n 是 k 的倍数，也等价于 k 能整除 n。
2. 因此，n 号门被切换的次数，等于 n 的约数个数。比如 12 号门会在第 1、2、3、4、6、12 轮被切换，因为这些数都能整除 12。
3. 再看切换次数和最终状态的关系。门最初是关闭的：切换 1 次会打开，切换 2 次会回到关闭，切换 3 次又打开。偶数次会互相抵消，奇数次会留下打开状态。
4. 所以我们只需要判断：n 的约数个数是奇数还是偶数。
5. 约数为什么会成对？如果 a 是 n 的约数，那么“n 除以 a”也是 n 的约数，并且 $a\times (n$ 除以 $a)=n$。例如 40 的约数可以配成 $1\times 40$、$2\times 20$、$4\times 10$、$5\times 8$，每一对贡献 2 个约数。
6. 如果 n 不是完全平方数，每个约数 a 都会配到另一个不同的约数“n 除以 a”。所有约数都两两成对，所以约数总数是偶数，门最后关闭。
7. 如果 n 是完全平方数，例如 $36=6\times 6$，约数 6 的搭档还是 6 自己。计数时 6 只能算一次，不会贡献一对不同约数，于是其他约数成对，再加上这个落单的平方根约数，总数就是奇数。
8. 因此，最后开着的门正好是 100 以内的完全平方数：$1^2$、$2^2$、$3^2$、...、$10^2$，也就是 1、4、9、16、25、36、49、64、81、100。

题面

有 25 匹马和 5 条赛道。每场比赛最多只能让 5 匹马一起跑，比赛结束后只知道这 5 匹马在本场里的第 1 名、第 2 名、第 3 名……没有秒表，也没有具体用时。

没有秒表的意思是：如果两匹马没有在同一场里直接比过，或者不能通过共同对手推出快慢，就不能凭感觉跨场比较。例如 A 组第 2 名不一定比 B 组第 2 名快。

假设每匹马速度稳定，同一匹马和同一批对手再跑，快慢关系不会变。问最少需要跑几场，才能保证确定 25 匹马中最快的 3 匹。

第一原则

没有秒表时，一场比赛只告诉我们参赛马之间的相对顺序。解题的第一原则是：如果已经能指出至少 3 匹马一定比某匹马快，那匹马就不可能进入全局前三。前 5 场先给每组内部排序，第 6 场比较五个组冠军，再用“至少 3 匹已知更快”的规则淘汰不可能者。剩下的马正好是所有仍可能成为第 2 或第 3 名的候选，最后一场把它们直接排出来。

详细解法

1. 先把 25 匹马任意分成 A、B、C、D、E 五组，每组 5 匹。每组跑 1 场，5 场之后得到组内顺序，例如 $A1>A2>A3>A4>A5$，$B1>B2>B3>B4>B5$。
2. 这 5 场是必要的：如果某匹马一次都没跑过，它完全可能是最快的马，我们就不可能保证找出前三。5 条赛道一次最多覆盖 5 匹马，所以至少要 5 场才能让 25 匹马都进入比较网络。
3. 第 6 场让五个组冠军 A1、B1、C1、D1、E1 比赛。为了叙述方便，假设结果是 $A1>B1>C1>D1>E1$。其他冠军顺序只是换个组名，推理完全一样。
4. 现在 A1 一定是全局第 1。原因很直接：A1 在 A 组赢过 A2 到 A5，又在冠军赛赢过 B1、C1、D1、E1；而其他组内的马又都输给各自冠军，所以没有任何马能比 A1 快。
5. 接着淘汰不可能进前三的马。D1 已经输给 A1、B1、C1，D 组其他马又输给 D1，所以 D 组全体至少被 3 匹马压住；E 组同理更不可能进前三。
6. C 组里，C1 只确定输给 A1、B1，所以它还可能是第 3；但 C2 输给 C1，同时也被 A1、B1 压住，已经有 3 匹已知更快，C2 到 C5 都淘汰。
7. B 组里，B1 只确定输给 A1，可能是第 2；B2 确定输给 B1 和 A1，仍可能是第 3；B3 输给 B1、B2，再加上 A1，至少 3 匹更快，所以 B3 到 B5 淘汰。
8. A 组里，A2 可能是第 2，A3 可能是第 3；A4 已经输给 A1、A2、A3，至少 3 匹更快，所以 A4、A5 淘汰。
9. 因此，除已确定第 1 的 A1 之外，仍可能成为全局第 2 或第 3 的马正好是 A2、A3、B1、B2、C1。这不是随便挑的 5 匹，而是所有没有被“至少 3 匹已知更快”排除的马。它们也确实都还可能：A2、B1 可能争第 2；A3、B2、C1 都可能在某种符合前 6 场结果的速度关系里成为第 3。
10. 第 7 场让 A2、A3、B1、B2、C1 同场比赛。它们中的第 1 名就是全局第 2，因为 A1 已经确定第 1；它们中的第 2 名就是全局第 3，因为其他所有马都已被证明不可能进前三。
11. 为什么 6 场还不够？如果总共只跑 6 场，那么前 5 场必须让 25 匹马各跑一次，否则没跑过的马仍可能是最快；于是前 5 场只能形成 5 个小组，第 6 场又必须比较 5 个小组冠军来确定第 1。冠军赛之后，A2 可能比 B1 快，也可能比 B1 慢；A3、B2、C1 之间也有一些跨组关系未知。存在多个都符合前 6 场结果的世界，所以必须再跑一场把这些候选直接比较清楚。于是最少 7 场，且 7 场方案已经给出。

题面

房间里有 100 个关闭的盒子，盒子外面编号为 1 到 100。盒子里面各放一张号码纸条，纸条上的号码也是 1 到 100，并且每个号码恰好出现一次。也就是说，盒子编号和盒内号码之间形成了一个随机配对。

外面有 100 名囚犯，也编号为 1 到 100。第 i 名囚犯的目标，是在盒子里找到写着 i 的那张纸条。

囚犯可以在进房间前一起商量一个统一策略。之后他们一个接一个单独进房；每个人最多只能打开 50 个盒子，可以看见打开盒子里的号码，但离开前必须把盒子恢复原状，不能移动纸条，不能留下记号，也不能把看到的信息告诉后面的人。

如果 100 名囚犯全都在自己的 50 次机会内找到自己的号码，就算全员成功；只要有 1 人失败，就算整体失败。问应该采用什么策略，才能让全员成功的概率尽可能高？这个概率大约是多少？

第一原则

把“盒子 k 里面写着号码 j”看成一支箭头 $k\to j$。因为每个号码只出现一次，每个盒子也只有一张纸条，所以这些箭头不会分叉，最终会分解成若干个循环。囚犯 i 从 i 号盒开始，再打开刚看到的号码对应的盒子，等于沿着包含 i 的那个循环往前走。若这个循环长度是 L，他会在第 L 次打开时看到自己的号码。因此每个人能否成功，只取决于自己所在循环是否不超过 50；全员成功等价于整个置换里没有长度超过 50 的循环。

详细解法

1. 策略很简单：第 i 名囚犯先打开 i 号盒子。如果盒子里正好是 i，他立刻成功离开。
2. 如果 i 号盒里写的是 j，就把 j 当作下一个盒子编号，继续打开 j 号盒。若里面又写着 k，就再打开 k 号盒。一直按“刚看到的号码就是下一次要开的盒子编号”走下去，最多走 50 步。
3. 为什么这不是乱走？因为盒内号码给了一个指针。比如 7 号盒写 1，1 号盒写 42，42 号盒写 7，那么 $7\to 1\to 42\to 7$ 是一个长度为 3 的循环。囚犯 7 依次打开 7、1、42 号盒，就会在第 3 次看到 7。
4. 更一般地说，囚犯 i 的路径一定留在包含 i 的同一个循环里。循环没有岔路，也不会提前跳到别的循环；走完整个循环时，最后一个盒子里必然写着 i，于是他找到自己的号码。
5. 所以，如果囚犯 i 所在的循环长度 $L\le 50$，他一定会在 50 次以内成功；如果 $L>50$，他需要走到第 L 次才会看到 i，而题目只给 50 次，所以他一定失败。
6. 整体要求是 100 人全都成功。因此不是“多数人成功”就够，而是每一个循环都必须短到不超过 50。换句话说，全员成功当且仅当随机排列没有长度为 51、52、...、100 的循环。
7. 接下来估计概率。对一个固定的 $k>50$ 来说，随机置换里出现长度为 k 的循环的概率是 $\frac{1}{k}$。直观上，可以先选出这 k 个元素，把它们排成一个环，再随意排列剩下元素；做完计数后正好得到 $\frac{1}{k}$。
8. 当 $k>50$ 时，两个这样的长循环不可能同时存在，因为它们的长度加起来会超过 100。所以失败概率就是出现某个长循环的概率之和：$\frac{1}{51}+\frac{1}{52}+\ldots +\frac{1}{100}$，约为 0.688172。
9. 因此成功概率是 $1-(\frac{1}{51}+\frac{1}{52}+\ldots +\frac{1}{100})$，约为 0.311828，也就是约 $31.18\%$。这不是保证成功，但已经远远高于每个人随便开 50 个盒子的全员成功概率。

题面

一座岛上住着一群完全理性的岛民。每个人都能看见其他所有人的眼睛颜色，却看不见自己的眼睛颜色。

岛上有一条规则：只要某人能确定自己是蓝眼，就必须在下一个清晨离岛；如果还不能确定，就不能因为猜测而离岛。

岛民之间不能讨论眼睛颜色，也不能用暗号传递信息。他们都知道这些规则，也知道其他人同样理性、同样知道这些规则。

某天傍晚，一个诚实的外来者当着所有岛民的面公开宣布：岛上至少有一个蓝眼人。大家都亲耳听见，也知道别人都亲耳听见。

如果实际上一共有 c 个蓝眼人，从公告后的第一个清晨算第 1 天，蓝眼人会在第几天离岛？为什么一句看似大家早就知道的话会改变局面？

第一原则

关键不是普通知识，而是公共知识。公共知识的意思是：所有人知道这件事，所有人也知道所有人知道这件事，并且这种“知道别人知道”的层级可以一直往下推。公开宣布把“至少一个蓝眼人”变成共同的推理起点；之后每一个没有人离开的清晨，都会排除一个更小的蓝眼人数。

详细解法

1. 先看最小情况。若 $c=1$，唯一的蓝眼人看不到任何其他蓝眼人。外来者说至少有一个蓝眼人，而他看不到别人是蓝眼，所以只能推出自己是蓝眼。他会在第 1 天清晨离岛。
2. 再看 $c=2$。每个蓝眼人都看到另一个蓝眼人。任意一个蓝眼人会想：如果我不是蓝眼，那么我看到的那个人就是唯一蓝眼人；按 $c=1$ 的推理，他会在第 1 天清晨离岛。可是第 1 天没人离岛，所以“我不是蓝眼”被排除。两名蓝眼人都会在第 2 天清晨离岛。
3. $c=3$ 时，每个蓝眼人都看到另外两个蓝眼人。他会想：如果我不是蓝眼，那么真实情况就是 $c=2$，那两个人应该在第 2 天清晨离岛。若第 1 天、第 2 天都没人离岛，他就知道自己也必须是蓝眼。于是三名蓝眼人在第 3 天清晨一起离岛。
4. 一般情况用归纳法。假设当蓝眼人数为 k 时，所有蓝眼人会在第 k 天清晨一起离岛。现在有 $k+1$ 个蓝眼人。每个蓝眼人都看到 k 个蓝眼人，并考虑“如果我不是蓝眼，那么只有 k 个蓝眼人”。按照归纳假设，那 k 个人会在第 k 天清晨离岛。
5. 如果第 k 天清晨仍然没人离岛，这个假设就错了；每个蓝眼人都能推出自己也是蓝眼。因此 $k+1$ 个蓝眼人会在第 $k+1$ 天清晨一起离岛。由 $c=1$ 的起点不断推出去，得到：有 c 个蓝眼人时，他们第 c 天清晨一起离岛。
6. 公开宣布为什么有用？因为在 c 大于 1 时，很多人确实已经能看见蓝眼人，但他们未必知道别人也知道这一点。例如 $c=2$ 时，每个蓝眼人都能看到一个蓝眼人，却会担心对方看到的是零个蓝眼人。公开宣布保证了即使在这种想象世界里，对方也听到了“至少一个蓝眼人”，所以第 1 天的推理能够启动，后面的沉默才会逐日变成证据。

题面

农夫、狼、羊、菜一开始都在左岸，目标是把它们全部送到右岸。船很小，每次过河必须有农夫在船上掌舵，船上除了农夫以外最多只能再带一个对象；农夫也可以自己空船返回。

危险只会发生在农夫不在的岸上：如果狼和羊单独留下，狼会吃羊；如果羊和菜单独留下，羊会吃菜。狼和菜在一起没有危险，因为它们彼此不吃对方。

问题是：在每一次过河之后，左右两岸都仍然安全的前提下，农夫应该按什么顺序摆渡，才能把狼、羊、菜全部带到右岸？

这道题里的“羊”也常被英文版本写成 goat，中文有时译作山羊或绵羊。名字不重要，重要的是它同时夹在两个冲突之间：狼会吃它，它又会吃菜。

第一原则

这不是速度题，而是状态约束题。先从第一原则看规则：农夫在某一岸时，可以看住那一岸；农夫离开后，那一岸必须自己安全。因此每次摆渡后都要检查左右两岸，尤其是没有农夫的那一岸。羊是唯一同时参与两个危险组合的对象：狼-羊危险，羊-菜也危险，所以羊不能被简单地放在某一边不管。它必须反复充当“冲突隔离物”：先把羊移走，避免左岸羊菜出事；带狼过去后又把羊带回，避免右岸狼羊出事；最后再把羊送到右岸。

详细解法

1. 第 1 次：农夫带羊从左岸到右岸。安全检查：左岸剩狼和菜，它们不互相伤害；右岸有农夫和羊，也安全。为什么先带羊？因为如果先带狼，左岸会留下羊和菜；如果先带菜，左岸会留下狼和羊，都会出事。
2. 第 2 次：农夫自己从右岸回左岸。安全检查：右岸只有羊，没有狼或菜，安全；左岸有农夫、狼、菜，农夫在场且狼菜本来不冲突。
3. 第 3 次：农夫带狼从左岸到右岸。安全检查：左岸只剩菜，安全；右岸有农夫、狼、羊，因为农夫在场，狼不能吃羊。
4. 第 4 次：农夫必须把羊从右岸带回左岸。安全检查：右岸只剩狼，安全；左岸有农夫、羊、菜，因为农夫在场，羊不能吃菜。这里不能空船回，因为那会把狼和羊单独留在右岸。
5. 第 5 次：农夫带菜从左岸到右岸。安全检查：左岸只剩羊，安全；右岸有农夫、狼、菜，狼和菜不冲突，所以安全。
6. 第 6 次：农夫自己从右岸回左岸。安全检查：右岸留下狼和菜，仍然不冲突；左岸有农夫和羊，安全。
7. 第 7 次：农夫带羊从左岸到右岸。安全检查：左岸清空；右岸有农夫、狼、羊、菜。即使狼、羊、菜都在同一岸，农夫也在场看管，所以完成。
8. 把路线连起来就是：羊去、空回、狼去、羊回、菜去、空回、羊去。羊之所以来回，是因为它是两条禁忌边的公共端点：既不能和狼无人看管，也不能和菜无人看管。

题面

左岸有 3 名传教士和 3 名野人，他们都要安全到达右岸。开始时船也在左岸，终点要求 6 个人全部在右岸。

船一次最多载 2 人，至少载 1 人，不能空船移动。传教士和野人都会划船，所以任意 1 人或 2 人只要在船上，就能把船划到另一岸。

安全规则只看两岸：任意一岸只要传教士人数大于 0，就不能让野人数超过传教士数。换句话说，某一岸合法当且仅当 $M=0$ 或 $M\ge C$，其中 M 表示传教士数，C 表示野人数。

每一次船靠岸后，都要同时检查左岸和右岸。要求给出一条完整路线，使过程中从不出现不合法状态，并最终全部过河。

第一原则

把问题先拆成状态，而不是凭感觉搬人。一个状态可以写成“左岸有几个 M、几个 C，船在哪一岸”；右岸人数由总数 3M3C 自动算出。合法状态必须让左右两岸都满足 $M=0$ 或 $M\ge C$。船的容量限制决定每次只能移动 1 人或 2 人；船的位置决定下一步只能从船所在的岸出发。因此回程不是浪费动作，而是把船带回还没运完人的那一岸，同时保持两岸合法。

详细解法

1. 用 M 表示传教士，用 C 表示野人。记住检查规则：某一岸没有 M 时安全；有 M 时，必须保证 M 的数量不少于 C。
2. 开始状态是左岸 3M3C、右岸 0M0C、船在左岸。目标状态是左岸 0M0C、右岸 3M3C、船在右岸。
3. 为什么一定会有回程？船不能自己回来，也不能隔空传递。如果船到了右岸，而左岸还剩人，就必须让某个已经到右岸的人把船划回左岸，后面的人才有船可用。
4. 第 1 步，CC 去：左岸变成 3M1C，右岸变成 0M2C。右岸没有 M，所以 2 个 C 在那里也合法。
5. 第 2 步，C 回：左岸 3M2C，右岸 0M1C。船回到左岸，左右两岸仍然合法。
6. 第 3 步，CC 去：左岸 3M0C，右岸 0M3C。先把 C 集中到右岸，可以为后面移动 M 腾出安全空间。
7. 第 4 步，C 回：左岸 3M1C，右岸 0M2C。船再次回到左岸，准备运送传教士。
8. 第 5 步，MM 去：左岸 1M1C，右岸 2M2C。两岸都是 $M=C$，所以安全。
9. 第 6 步，MC 回：左岸 2M2C，右岸 1M1C。只让 M 回会让右岸 1M2C，不合法；只让 C 回会让左岸 1M2C，不合法，所以要一 M 一 C 同回。
10. 第 7 步，MM 去：左岸 0M2C，右岸 3M1C。左岸没有 M，不会有人被吃；右岸 3M 大于 1C，也安全。
11. 第 8 步，C 回：左岸 0M3C，右岸 3M0C。让 C 回来，是为了接走左岸最后的 C；左岸仍然没有 M，所以安全。
12. 第 9 步，CC 去：左岸 0M1C，右岸 3M2C。右岸 3M 大于 2C，安全。
13. 第 10 步，C 回：左岸 0M2C，右岸 3M1C。最后一次把船带回左岸，准备收尾。
14. 第 11 步，CC 去：左岸 0M0C，右岸 3M3C。右岸 $M=C$，左岸为空，所有人安全过河。
15. 完整路线就是：CC 去、C 回、CC 去、C 回、MM 去、MC 回、MM 去、C 回、CC 去、C 回、CC 去。每一步都只载 1 人或 2 人，并且每一步后左右两岸都合法。

题面

100 个人排成一列，每个人头上戴一顶帽子，帽色只有黑、白两种。帽子的分配可以是任意的，大家事先不知道具体排列。

每个人只能看见自己前面所有人的帽子，看不见自己的帽子，也看不见自己身后人的帽子。因此队尾第 100 人能看见前面 99 顶帽子，队首第 1 人一顶也看不见。

他们必须从队尾开始，按第 100 人、第 99 人、一直到第 1 人的顺序，依次大声说出自己帽子的颜色。每个人都能听到身后已经说过的所有答案。

在开始前，100 个人可以商量一套固定策略。开始后只能按顺序说“黑”或“白”，不能用停顿、音量或别的暗号。问无论帽子怎样分配，最多能保证多少人说对。

第一原则

这题的关键是把最后一人的回答当成 1 位校验码，而不是当成真正的猜帽子。约定黑帽记为 1，白帽记为 0，黑帽数量的奇偶性就是所有这些 1 相加后除以 2 的余数。第 100 人看得见前面 99 顶帽子，可以报告它们的奇偶性；这个校验位不包含他自己的帽子，所以他可能错。但从第 99 人开始，每个人都能把“总奇偶”和“自己前方可见奇偶”相比较，剩下唯一不确定的那一顶就是自己的帽子。

详细解法

1. 先统一约定：黑帽记为 1，白帽记为 0；如果第 100 人看到前面 99 人中黑帽数为奇数，就报“黑”，表示校验位为 1；如果看到偶数，就报“白”，表示校验位为 0。反过来约定也可以，但所有人必须一致。
2. 第 100 人为什么不能保证正确？因为他看不见自己的帽子。对他来说，前面 99 顶帽子完全相同的两个世界可能同时存在：一个世界里他戴黑帽，另一个世界里他戴白帽。他在这两个世界会听不到任何先前信息、看到同一幅画面，却必须说同一个词，所以不可能同时答对。
3. 第 99 人听到第 100 人给出的校验位，知道第 1 到第 99 人的黑帽总数是奇数还是偶数。他自己又能看见第 1 到第 98 人的帽子，所以能数出这些可见帽子的奇偶性。
4. 如果第 99 人看到的奇偶性已经等于总奇偶性，说明他自己没有额外贡献 1，他就是白帽；如果两者不同，说明差的那 1 来自他的帽子，他就是黑帽。
5. 第 99 人说出的帽色是确定正确的。于是第 98 人不仅知道原来的总奇偶性，也知道第 99 人这一顶帽子是什么颜色，可以把它从校验信息中扣掉，得到第 1 到第 98 人的黑帽奇偶性。
6. 同理，第 98 人再把自己前方第 1 到第 97 人的可见奇偶性与这个更新后的校验位比较，就能推出自己的帽色。之后每个人都重复同一个步骤：先扣掉身后已经确定的帽子，再比较自己前方可见的奇偶性。
7. 因此第 99 人到第 1 人每一步都只剩“自己这一顶帽子”一个未知量，全部可以保证正确。第 100 人的回答承担编码任务，可能碰巧正确，但不能被保证。

题面

有一根长度为 L 的直木棍，左端记为 0，右端记为 L。若干只蚂蚁分别站在木棍上的已知位置 x_i，且 $0<x_i<L$。所有蚂蚁爬行速度相同，记为 v。

每只蚂蚁一开始只能朝左或朝右爬。蚂蚁爬到任意一个端点时，会立刻从木棍上掉下去；两只蚂蚁在木棍上相遇时，会同时掉头，继续以同样速度爬行。

如果题目没有告诉你每只蚂蚁一开始朝哪边，只要求判断“所有蚂蚁最早可能什么时候全部掉下去”和“最晚可能什么时候全部掉下去”，应该怎样算？如果初始方向已经给定，又该怎样避免模拟每一次相遇？

第一原则

第一原则是先分清“位置”与“身份”。两只同速蚂蚁迎面相遇时，如果它们都掉头，那么左边会有一只蚂蚁向左走，右边会有一只蚂蚁向右走；如果让它们直接穿过，左边也会有一只向左走，右边也会有一只向右走。对于木棍上每个时刻有哪些位置被蚂蚁占着，这两种描述完全一样。差别只在于我们把哪只蚂蚁叫作 A、哪只叫作 B：掉头模型像是两只蚂蚁反弹，穿过模型像是两只蚂蚁交换了名字。

详细解法

1. 先看两只蚂蚁的局部相遇。假设 A 从左向右走，B 从右向左走，并且速度相同。相遇前，它们之间的距离等速缩短；相遇后，如果按题意掉头，A 往左、B 往右。
2. 现在换一种说法：相遇时不让它们掉头，而是让它们互相穿过。穿过后，左边那条轨迹继续向左，右边那条轨迹继续向右。木棍上看到的“哪里有蚂蚁”完全不变，只是这条轨迹上的名字从 A 变成了 B。
3. 因为题目通常只问“什么时候全部掉下去”，不问“名叫 A 的那只从哪端掉下去”，所以身份交换不会影响答案。我们可以把每只蚂蚁都想象成不受碰撞影响，一直沿初始方向直走到端点。
4. 如果每只蚂蚁的初始方向已经给定，就按穿过模型逐只计算：向左的蚂蚁需要 $x_i/v$ 时间掉下，向右的蚂蚁需要 ($L-x_i)/v$ 时间掉下。所有蚂蚁全部掉下的时间，是这些时间里的最大值。
5. 如果初始方向未知，要让全部蚂蚁尽量早掉下，每只蚂蚁都应选择较近的端点。第 i 只蚂蚁最快可在 $min(x_i, L-x_i)/v$ 后掉下；但必须等最后一只也掉下，所以最早全落时间是所有这些较近端时间的最大值。
6. 如果初始方向未知，要让全部蚂蚁尽量晚掉下，只需要让某只蚂蚁走到它能走到的最远端点，并且其他蚂蚁不会因为碰撞真正改变位置集合。因此最晚全落时间由最大远端距离决定，即 $max max(x_i, L-x_i)/v$。
7. 这就是这题不需要列碰撞时间表的原因：碰撞会改变身份标签，却不改变无标签的位置轨迹；掉落时间只由直走到端点的距离和速度决定。

题面

一个池塘里长着一种睡莲。题目约定：每过一天，睡莲覆盖的面积都会变成前一天的 2 倍。比如某天覆盖半个池塘，下一天就会覆盖整个池塘；某天覆盖四分之一池塘，下一天就会覆盖半个池塘。

现在知道，第 30 天观察时，睡莲刚好第一次铺满整个池塘。问：在第几天观察时，睡莲刚好覆盖了池塘的一半？

注意，题目问的是“半满是哪一天”，不是问睡莲最开始有多大，也不是问每天平均增加多少面积。

第一原则

翻倍增长最容易从结果往前倒推。正着看，一天后乘以 2；反着看，往前一天就除以 2。所以如果第 30 天是 1 个完整池塘，第 29 天一定是 $\frac{1}{2}$ 个池塘。这里不能把 30 天平均分成两半，因为指数增长不是每天增加同样多，而是每天按当前面积再翻一倍。

详细解法

1. 先把“满池”记成 1。这个 1 不是一片叶子的数量，而是整个池塘的面积比例：1 表示 $100\%$ 满池，$\frac{1}{2}$ 表示 $50\%$ 半池。
2. 题目说每天翻倍，意思是：明天的覆盖面积 = 今天的覆盖面积 × 2。例如今天是 $\frac{1}{4}$，明天就是 $\frac{1}{2}$；今天是 $\frac{1}{2}$，明天就是 1。
3. 已知第 30 天刚好铺满，所以第 30 天的面积比例是 1。
4. 现在反过来问第 30 天的前一天。既然第 29 天再翻倍会变成第 30 天，那么第 29 天 = 第 30 天 ÷ $2 = 1$ ÷ $2 = \frac{1}{2}$。
5. 因此第 29 天刚好半满。它只比满池早一天，因为从半满到满池只需要再翻一倍，而题目规定每天正好翻一倍。
6. 如果继续往前倒推，第 28 天是 $\frac{1}{4}$，第 27 天是 $\frac{1}{8}$。越靠近最后几天，面积增长越快，这正是指数增长的特征。

题面

一名工人要连续工作 7 天，工资是每天 1 段金条。你手里只有一根完整金条，它可以看成由 7 段等长的小段连在一起。

每天结束时都要结算一次：第 1 天结束时，工人手里必须刚好值 1 段；第 2 天结束时必须刚好值 2 段；一直到第 7 天结束时必须刚好值 7 段。

关键规则是：每天结算时，之前给出去的金条块可以拿回来，也可以换成别的金条块。也就是说，工人当天最后拿着的总价值要正确，不要求每天只能新增一小段。

为了满足 7 天的所有结算要求，最少需要切几刀？应该切成哪些长度？

第一原则

把每天累计工资看成 1 到 7 这些整数。1、2、4 是最小的二进制权重：每个整数都可以通过“拿或不拿”这些块来表示。因为 $7=1+2+4$，所以三块刚好覆盖 1 到 7；把一根金条切成三块只需要 2 刀。

详细解法

1. 先想清楚每天到底要表示什么。第 n 天结束时，工人手里的金条总价值必须等于 n 段，所以我们需要表示 1、2、3、4、5、6、7。
2. 如果切成 1、2、4 三块，就能用“选中某些块”的方式表示所有这些数：$1=1$，$2=2$，$3=1+2$，$4=4$，$5=4+1$，$6=4+2$，$7=4+2+1$。
3. 实际付款时不是每天永久多给一块，而是每天可以交换。第 1 天给 1；第 2 天给 2，并收回 1；第 3 天再把 1 给出去，此时工人有 $1+2$。
4. 第 4 天给 4，并收回 1 和 2；第 5 天再给 1；第 6 天给 2，并收回 1；第 7 天再给 1。每天结束时，工人手里的总价值分别是 1、2、3、4、5、6、7。
5. 为什么 2 刀是最少？0 刀只有 1 块，不能支付第 1 天；1 刀最多得到 2 块，哪怕两块长度随便切，也最多只能组成空、第一块、第二块、两块一起这几种总值，无法稳定覆盖 1 到 7 的 7 个正整数。
6. 所以 2 刀既能做到，又不可能再少，答案就是切 2 刀，得到 1、2、4 三块。

题面

你站在两扇外观相同的门前。恰好一扇门通向安全出口，另一扇门通向危险地点，你不能从门本身看出区别。

门口有两名守卫。两人都知道哪扇门安全，但其中一人永远说真话，另一人永远说假话。你不知道谁是真话守卫，也不知道谁是假话守卫。

你只能任选一名守卫，问他一个问题。问完后不能追问，也不能先试一扇门再回来。怎样提问，才能保证自己选到安全门？

第一原则

关键不是猜出谁诚实，而是把两种身份合成同一种结果。问“另一名守卫会怎么说”时，答案一定经过一次说谎：问到真话守卫，他会真实转述假话守卫的错误答案；问到假话守卫，他会把真话守卫的正确答案说反。两条路径都指向错误门，所以取相反门就是安全门。

详细解法

1. 先把两扇门起名为 A 门和 B 门。假设 A 门安全、B 门危险；如果现实相反，推理会完全对称。
2. 对任意一名守卫问：如果我问另一名守卫哪扇门安全，他会指哪扇？
3. 情况一：你问到真话守卫。他必须如实回答“假话守卫会怎么说”。假话守卫被问哪扇门安全时会说假话，因此会把危险门说成安全门。
4. 情况二：你问到假话守卫。另一名守卫是真话守卫，本来会指出真正的安全门；但假话守卫不能如实转述，所以会把这个答案说反，改指危险门。
5. 两种情况的组成方式不同，但输出相同：都得到危险门。既然守卫指给你的那扇一定是危险门，你就选择另一扇门。
6. 这道题的核心是“保证”。好问题不需要你知道守卫身份，因为不管身份怎样，回答都会落在同一个错误结果上。

题面

假设一年固定有 365 天，暂时忽略闰年；每个人的生日独立产生，并且落在任意一天的机会都一样。现在有 n 个人同时站在一个房间里。

问题不是问“有没有人和我同一天生日”，而是问这 n 个人里面任意两个人是否可能同一天生日。只要出现一对同生日，就算成功。

直觉常会猜要接近 183 人才有一半机会，因为 183 差不多是 365 的一半。但真实答案小得多：到 23 人时，至少一对同生日的概率已经超过 $50\%$。为什么会这样？

第一原则

直接计算“至少一对同生日”会遇到很多重叠情况：可能只有一对相同，也可能两对相同，还可能三个人同一天。更简单的做法是先算反面，也就是“所有人的生日都不同”。这个反面事件只有一种清晰要求：新人必须避开前面已经占用的生日。最后用 1 减去全不同的概率，就得到至少一对相同的概率。23 人让人意外，是因为人和人之间的潜在配对数增长很快：23 人不是只有 23 次机会，而是有 $23\times \frac{22}{2}=253$ 对可以发生相撞。

详细解法

1. 先把目标事件命名为 A：至少有两个人生日相同。它的反面不是“所有人都相同”，而是“任意两个人都不同”，也就是所有人的生日全都不同。
2. 为什么反面更好算？因为可以按人一个一个进房间。第 1 个人没有需要避开的生日，所以无论哪天都可以，概率是 $\frac{365}{365}$。
3. 第 2 个人要和第 1 个人不同，只需要避开 1 天，因此有 364 天可选，概率是 $\frac{364}{365}$。
4. 第 3 个人要和前 2 个人都不同，需要避开 2 个已经出现的生日，因此概率是 $\frac{363}{365}$。继续下去，第 k 个人要避开前面 $k-1$ 个生日，概率是 ($365-k+1)/365$。
5. 所以 n 个人生日全不同的概率是 $\frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \ldots \times (365-n+1)/365$。
6. 代入 $n=23$，要乘到 $\frac{343}{365}$，因为第 23 个人必须避开前面 22 个生日，还剩 $365-22=343$ 天可选。
7. 这个乘积约为 0.4927，也就是全都不同的概率约 $49.27\%$。
8. 现在回到原问题。至少一对同生日和全都不同是互补事件：二者必有一个发生，并且不能同时发生。因此至少一对同生日的概率是 $1-0.4927=0.5073$，约 $50.73\%$。
9. 再看为什么 23 会这么早。23 个人能组成 $23\times \frac{22}{2}=253$ 对。虽然每一对单独相同的概率只有 $\frac{1}{365}$，但可比较的对子已经很多；从逐个进房间的角度看，第 2 人避开 1 个生日，第 3 人避开 2 个生日，一直到第 23 人避开 22 个生日，总共是 $1+2+\ldots +22=253$ 个避让要求。这些小压力连乘起来，已经足以把全不同概率压到一半以下。
10. 22 人时全不同概率约 $52.43\%$，至少一对相同约 $47.57\%$；23 人时跨过一半。这就是经典答案不是 183，而是 23 的原因。

题面

一个家庭有两个孩子。为了把题目先说清楚，假设每个孩子是男孩或女孩的机会相同，并且两个孩子的性别互不影响。

现在问：在得到一些已知信息后，这个家庭两个孩子都是男孩的概率是多少。

版本 A：只知道“至少一个孩子是男孩”。版本 B：明确知道“较大的孩子是男孩”。

这两个说法听起来都在提供男孩信息，但它们筛掉的家庭不同，所以不能直接套同一个答案。

第一原则

条件概率要先问“已知条件把哪些情况留下了”。先列出原始等可能情况，再用条件过滤分母，最后在留下的情况里数成功情况。

详细解法

1. 第一步是给两个位置命名：大孩和小孩。B 表示男孩，G 表示女孩。
2. 原始样本空间有四种等可能情况：BB、BG、GB、GG。这里必须把 BG 和 GB 分开，因为“谁较大”是题目会用到的信息。
3. 版本 A 的条件是“至少一个是男孩”。它只排除 GG，留下 BB、BG、GB 三种等可能家庭。目标“两孩都是男孩”只对应 BB，所以概率是 $\frac{1}{3}$。
4. 版本 B 的条件是“较大的是男孩”。它直接固定了大孩这个位置，留下 BB、BG 两种等可能家庭。目标仍然只对应 BB，所以概率是 $\frac{1}{2}$。
5. 差别来自分母：版本 A 的分母是三个家庭，版本 B 的分母是两个家庭。条件概率改变的是“从哪里数”，不是只改变一句话里的关键词。
6. 如果题目只说“我看见一个孩子是男孩”或“家长提到一个男孩”，还缺少采样过程。随机看见一个孩子、家长主动选择说哪个孩子、只筛选有男孩家庭，可能对应不同分母。

题面

n 个人按 1 到 n 编号，围成一圈。1 号先报 1，2 号报 2，凡是报到 2 的人立刻离开；离开者的下一人重新从 1 开始报。

这个过程一直继续，直到只剩 1 个人。问题是：最后留下来的原始编号是多少？经典版本问 $n=100$ 时谁会幸存。

这里的规则非常重要：编号从 1 开始，第一次被淘汰的是 2 号，每次都是“隔一人淘汰一人”。

第一原则

先看人数是 2 的幂的情形：每完成一轮，人数刚好减半，新的起点仍然是当前圈里的第一个人，所以 1 号一路保持优势。若人数不是 2 的幂，就先淘汰掉多出来的 l 个人；这会把起点向后推到 $2l+1$，然后剩下的人数正好变成 2 的幂。

详细解法

1. 把幸存者记为 J(n)。先从最容易的情况开始：如果 $n=1$，唯一的人当然幸存，$J(1)=1$。
2. 如果 $n=8$，第一轮淘汰 2、4、6、8，剩 1、3、5、7；下一轮淘汰 3、7，剩 1、5；再淘汰 5，最后是 1。$n=16$、32、64 也一样，每轮都整齐减半，所以 $J(2^m)=1$。
3. 现在设 $n=2^m+l$，其中 $2^m$ 是不超过 n 的最大 2 的幂，l 是多出来的人数，满足 $0\le l<2^m$。
4. 先看前 l 次淘汰。因为从 1 号开始、每隔一人淘汰，前 l 个被淘汰者正好是 2、4、6、...、2l。
5. 淘汰这 l 个人后，还剩 $n-l=2^m$ 个人；下一位开始报 1 的人是 $2l+1$。剩下的人数已经是 2 的幂，所以这个“新起点”会像 1 号在 2 的幂人数中那样活到最后。
6. 因此 $k=2$、1 开始编号的约瑟夫环公式是 $J(n)=2l+1$。
7. $100=64+36$，所以 $l=36$，$J(100)=2\times 36+1=73$。
8. 二进制也能看见同一件事：n 的二进制是“最高位 $1 + l$ 的二进制”，而 $2l+1$ 等于把 l 左移一位再补 1；这就像把最高位的 1 移到最右边。100 是 $1100100_2$，左移最高位后得到 $1001001_2$，也就是 73。

题面

桌上有若干堆石子。两人轮流行动，每次必须选择其中一堆，并从这一堆里拿走至少 1 颗石子。

一次行动不能同时碰两堆，也不能把石子拿成负数；如果轮到某人时已经没有石子可拿，这个人就输。

问题是：只给出每堆石子的数量，怎样判断先手有没有必胜策略？如果有，第一步应该拿哪一堆、拿多少？

第一原则

把每堆石子数写成二进制，再逐位做异或：同一位上有奇数个 1，结果就是 1；有偶数个 1，结果就是 0。所有堆的异或和叫 $nim-sum$。$nim-sum$ 为 0 表示每个二进制位都已经成对平衡，当前玩家无论改动哪一堆，都会破坏某一位的平衡；$nim-sum$ 非 0 时，可以只改动一堆，把所有位重新配平。

详细解法

1. 第一步，把每堆石子数都看成二进制数，并计算 $pile1 \oplus pile2 \oplus \ldots$，这个结果就是 $nim-sum$。
2. $\oplus$ 可以理解成“不进位的逐位加法”：某一位出现奇数个 1，答案位是 1；出现偶数个 1，答案位是 0。
3. 如果 $nim-sum$ 为 0，先手必败。因为合法操作只能改变一堆，设这一堆从 old 变成 new；新的总异或会从 0 变成 $old \oplus new$。只要 old 和 new 不同，$old \oplus new$ 就不是 0。
4. 也就是说，先手从 0 态走出后，一定把局面交成非 0 态。后手只要每次把非 0 态恢复成 0 态，就能一直保持优势。
5. 如果 $nim-sum$ 非 0，先手必胜。看 $nim-sum$ 最高的那个 1 位；在这一位上，必定有某一堆也是 1，否则这些堆异或不可能得到 1。
6. 选择这样一堆，记为 pile，把它改成 $pile \oplus nim-sum$。这个新值一定小于 pile，因为最高的差异位会从 1 变成 0，所以这是一次合法的“减少”。
7. 改完后，总异或变成 $nim-sum \oplus pile \oplus (pile \oplus nim-sum) = 0$。于是先手一步把局面交给对方的必败态。
8. 例子 3、4、5：写成二进制是 011、100、101。逐位异或得到 010，也就是 2，所以先手有必胜招。
9. $nim-sum$ 的最高 1 在 2 的位置，堆 3 的二进制 011 在这一位是 1。把 3 改成 $3 \oplus 2 = 1$，也就是从这一堆拿走 2 颗。
10. 新局面是 1、4、5，二进制为 001、100、101；$001 \oplus 100 \oplus 101 = 000$。之后无论对手怎么拿，你都再次把 $nim-sum$ 变回 0。

题面

有一个普通的 8x8 棋盘，一共有 64 个小方格。现在把左上角和右下角这两个对角角落拿掉，棋盘上还剩 62 个小方格。

你手里有 31 张 1x2 骨牌。每张骨牌的形状正好能盖住两个共边相邻的小方格：可以横着放，也可以竖着放，但不能斜着放、不能重叠、不能伸出棋盘外。

问题是：能不能把这 31 张骨牌全部放上去，并且刚好把残缺棋盘的 62 个小方格全部盖住？

从面积看，31 张骨牌正好覆盖 $31x2=62$ 个格子，似乎没有问题。但这道题的关键是：面积够，只是必要条件，不一定足够。

第一原则

把棋盘按普通国际象棋棋盘那样黑白相间染色。两个共边相邻的格子颜色一定不同，所以任何一张 1x2 骨牌，无论横放还是竖放，都必然覆盖一黑一白。也就是说，铺一张骨牌会同时消耗 1 个黑格和 1 个白格，黑白消耗量始终相等。这个“每一步都保持的数量关系”就是不变量。

详细解法

1. 先给完整 8x8 棋盘染成黑白相间。因为每一行颜色交替，而且一共有偶数个格子，所以完整棋盘里黑格 32 个、白格 32 个。
2. 为什么相邻两格一定一黑一白？从任意一个格子往左、右、上、下移动一步，棋盘颜色都会翻转一次。因此一张覆盖两个共边相邻格子的 1x2 骨牌，不可能盖住两个同色格。
3. 再看被拿掉的两个角。左上角和右下角在同一条主对角线上；从左上走到右下，要向右走 7 步、向下走 7 步，总共移动 14 步。移动偶数步后颜色翻转偶数次，最后颜色和起点相同，所以这两个对角角落同色。
4. 假设这两个角都是黑色。完整棋盘原来有 32 黑 32 白，拿掉两个黑角后，剩下 30 个黑格和 32 个白格。如果你一开始把角染成白色，结论只会变成 32 黑 30 白，本质完全一样。
5. 现在假设真的能铺满。31 张骨牌每张都覆盖一黑一白，所以一共必须覆盖 31 个黑格和 31 个白格。
6. 但残缺棋盘上实际只有 30 个某种颜色的格子，另一种颜色有 32 个。骨牌需要的黑白数量是 31 比 31，棋盘提供的黑白数量却是 30 比 32。
7. 这个矛盾不是某种摆法没找到，而是所有摆法都绕不过去的限制。因此这个残缺棋盘不可能被 31 张 1x2 骨牌铺满。

题面

桌上有两个外观完全相同的信封。一个信封里的钱正好是另一个的两倍。你随机拿到其中一个信封，可以保留它，也可以换成另一个信封。

有人说：设我手里的金额是 x。另一个信封要么是 2x，要么是 $\frac{x}{2}$，而且这两种情况看起来各有一半机会。所以换信封后的期望是 $\frac{1}{2}$·$2x+\frac{1}{2}$·$\frac{x}{2}=1.25x$，比 x 大，似乎永远应该换。

可是如果这个推理对你手里的信封成立，对另一个信封也应该成立：无论你拿到哪个信封，都能说“换过去更赚”。两个信封完全对称，却都像是应该换，这就是双信封悖论。

问题是：这个 1.25x 的期望推理到底错在哪里？在没有更多信息时，换信封是更好、更坏，还是没有区别？

第一原则

关键是先分清“没看金额前”和“看见具体金额 x 后”是两个不同问题。没看金额前，如果两个金额已经固定为 a 和 2a，再随机把一个给你，两个信封完全对称，换只是把当前信封和另一个信封互换，期望不会变。看见 x 之后，问题变成条件概率：x 是较小金额的概率是多少？朴素公式把同一个 x 在一条分支里当成小金额、在另一条分支里当成大金额，又直接假设两条分支各占 $\frac{1}{2}$；这个“各一半”不是由题目自动给出的，必须来自金额的生成规则或先验分布。

详细解法

1. 先看最朴素、信息最少的模型：出题人先放好两个金额 a 和 2a，然后随机把其中一个信封给你。你拿到 a 的概率是 $\frac{1}{2}$，拿到 2a 的概率也是 $\frac{1}{2}$。
2. 在这个模型里，不换的期望是 $\frac{1}{2}$·$a+\frac{1}{2}$·$2a=1.5a$。换信封后，你原来拿到 a 就会得到 2a，原来拿到 2a 就会得到 a，所以换的期望也是 $\frac{1}{2}$·$2a+\frac{1}{2}$·$a=1.5a$。换与不换完全对称。
3. 注意这里的 a 是“较小金额”，在两种分支里含义不变。朴素错误推理里的 x 不一样：x 是“我看到的金额”。如果 x 是小金额，另一个是 2x；如果 x 是大金额，另一个是 $\frac{x}{2}$。它在两条分支里的身份不同。
4. 因此看见 x 后，正确写法应该是：设 p 是“在已经看到 x 的条件下，x 是较小金额”的概率。另一个信封的条件期望是 p·$2x+(1-p)$·$\frac{x}{2}$。
5. 什么时候应该换？把这个期望和 x 比较：p·$2x+(1-p)$·$\frac{x}{2}>x$ 等价于 $p>\frac{1}{3}$。也就是说，只有当你有理由相信“x 是较小金额”的概率超过 $\frac{1}{3}$ 时，换才有正期望。
6. p 不能凭空得到。它取决于金额是怎么生成的：较小金额 a 是从哪些数里抽的？不同金额出现的先验概率是多少？有没有上限、下限或整数限制？这些规则会改变你看到 x 后对“x 是小金额还是大金额”的判断。
7. 举个直观例子：如果出题人只可能准备 10 和 20 两种金额，那么你看到 10 时一定拿到小金额，应该换；看到 20 时一定拿到大金额，不应该换。看到金额以后，决策依赖生成规则，而不是固定地“永远换”。
8. 所以悖论的结论不是“换一定亏”，也不是“换一定赚”。在没有额外信息、也没看到金额时，两个信封对称，换不换一样；在看到具体金额后，必须补充先验或生成机制，才能计算是否值得换。