第 2 章 脑筋急转弯

原著： Xinfeng Zhou，A Practical Guide to Quantitative Finance Interviews（2008）。

本页由 GPT 视觉模型直接依据扫描页识别、翻译和公式排版。

查看本页原始扫描图

本章涵盖的问题仅需要常识、逻辑推理和基础数学知识（不超过高中水平）即可解答。从某种意义上说，它们是真正的脑筋急转弯，而非披着外衣的数学题。虽然这些脑筋急转弯不要求特定的数学知识，但其难度并不亚于其他量化面试题。部分题目考察你的分析能力和通用解题能力；部分题目要求你跳出常规思维；还有一部分题目则要求你用创造性的方式运用基础数学技巧来求解。在本章中，我们将回顾一些面试题，以解释量化面试中可能遇到的脑筋急转弯的一般类型。

2.1 简化问题

如果原问题过于复杂，你无法立刻想到解法，可以尝试找出该问题的一个简化版本，并从这个简化版本入手。通常你可以从最简单的子问题开始，然后逐渐增加复杂度。开始时你不需要有一个明确的计划。只需尝试求解最简单的案例，并分析你的推理过程。通常你会发现一个模式，这个模式会为你解决整个问题提供指导。

海盗分金币

五名海盗洗劫了一个装满 100 枚金币的宝箱。作为一群民主的海盗，他们同意按以下方法分赃： 最资深的海盗将提出一个分配方案。然后所有海盗（包括最资深的海盗）进行投票。如果至少有 50% 的海盗（在这个例子中是 3 名海盗）接受该方案，则按提议分配金币。否则，最资深的海盗将被喂鲨鱼，然后由下一名最资深的海盗重新开始这个过程……这个过程会一直重复，直到某个方案被通过。你可以假设所有海盗都完全理性：他们首先想保住性命，其次想获得尽可能多的金币。最后，作为嗜血的海盗，如果面临两种结果相同的选择，他们希望船上的海盗数量更少。 最终金币将如何分配？ 解法： 如果你没有学习过博弈论或动态规划，这个策略问题可能会让你望而生畏。如果 5 个海盗的问题看起来很复杂，我们总是可以先通过减少海盗的数量来简化问题。由于 1 个海盗的情况显而易见，让我们从 2 个海盗开始。资深

查看本页原始扫描图

海盗（标记为 2）可以声称获得所有金币，因为他将始终获得自己（海盗 2）和海盗 1 的 50% 的选票，而海盗 1 将一无所有。让我们增加一个更资深的海盗，海盗 3。他知道如果他的计划被否决，海盗 1 将一无所有。但如果他什么都不给海盗 1，海盗 1 会乐于杀死他。所以海盗 3 会分给海盗 1 一枚金币，自己保留剩余的 99 枚金币。在这种策略下，该计划将获得海盗 1 和海盗 3 的 2 票（即三分之二的选票）。如果增加了海盗 4，他知道如果他的计划被否决，海盗 2 将一无所有。所以如果海盗 4 分给海盗 2 一枚金币，海盗 2 就会满足于得到一枚金币（因为否则他将一无所有）。因此，海盗 4 应该分给海盗 2 一枚金币，自己保留剩余的 99 枚金币。他的计划将获得海盗 2 和海盗 4 的 50% 的选票（即 2 票中的 2 票）而获得批准。现在我们终于来到了 5 个海盗的情况。

海盗 5 知道如果他的计划被否决，海盗 3 和海盗 1 都将一无所有。所以他只需要分给海盗 1 和海盗 3 各一枚金币来获得他们的选票，自己保留剩余的 98 枚金币。如果他这样分配金币，他将获得五分之三的选票：来自海盗 1、海盗 3 以及他自己。一旦我们从一个简化的版本开始并逐步增加复杂性，答案就变得清晰可见。实际上，在 \(n=5\) 的情况之后，一个清晰的模式已经出现，我们不需要 在 5 个海盗处停止。对于任何 \(2n+1\) 个海盗的情况（这里 \(n\) 应该小于 99），最资深的海盗将分给海盗 1、3、…、以及 \(2n-1\) 各一枚金币，并为自己保留剩下的所有金币。

老虎和绵羊

一百只老虎和一只绵羊被放在一个只有草的魔法岛上。老虎可以吃草，但它们更愿意吃绵羊。假设：A. 每次只有一只老虎可以吃掉一只绵羊，并且那只老虎在吃掉绵羊后自己会变成一只绵羊。B. 所有老虎都很聪明且完全理性，它们都想生存。那么绵羊会被吃掉吗？解法： 100 是一个很大的数字，所以我们再次从一个简化的版本开始解决问题。如果只有 1 只老虎（\(n=1\)），它肯定会吃掉绵羊，因为它不必担心自己被吃掉。那 2 只老虎呢？由于两只老虎都完全理性，任何一只老虎可能都会思考：如果它吃了绵羊会发生什么。任何一只老虎可能都在想：“如果我吃了绵羊，我就会变成一只绵羊；然后我会被另一只老虎吃掉。”所以为了保证最高的生存几率，没有一只老虎会吃掉绵羊。如果有 3 只老虎，绵羊会被吃掉。因为每只老虎都会意识到：一旦它变成一只绵羊，就会剩下 2 只老虎，而它不会被吃掉（因为两只老虎的情况是稳定的，谁也不会吃谁）。所以第一只想明白这一点就会吃掉绵羊。

如果有 4 只老虎，每只老虎都会明白：

补充说明： 用数学归纳法的思想来理解这个模式更清晰。将老虎视为状态，状态 \(S_n\) 表示有 \(n\) 只老虎和 1 只绵羊。

* 基本情况： \(S_1\)，老虎肯定吃羊（因为没有其他老虎）。

* 递推关系： 如果某只老虎吃了羊，它就变成了一只羊，状态变为 \(S_{n-1}\)。所以，对于状态 \(S_n\)，如果 \(S_{n-1}\) 的结果是羊不会被吃，那么当前的老虎就会去吃羊（因为吃掉后自己是安全的）；如果 \(S_{n-1}\) 的结果是羊会被吃，那么当前的老虎就不会去吃羊（因为吃掉后自己会被吃）。

* 归纳结论： 由此可得：

* \(S_1\)：吃

* \(S_2\)：不吃（因为 \(S_1\) 中羊会被吃，即自己会变羊并被吃）

* \(S_3\)：吃（因为 \(S_2\) 中羊安全，即自己变羊后安全）

* \(S_4\)：不吃（因为 \(S_3\) 中羊会被吃）

简而言之，奇数只老虎时，羊会被吃；偶数只老虎时，羊不会被吃。

查看本页原始扫描图

如果它吃了绵羊，自己就会变成一只绵羊。由于还有 3 只其他老虎，它会被吃掉。所以为了保证最高的生存几率，没有老虎会吃绵羊。 按照相同的逻辑，我们可以自然地证明：如果老虎的数量是偶数，绵羊不会被吃掉；如果老虎的数量是奇数，绵羊会被吃掉。对于 \(n=100\)（偶数）的情况，绵羊不会被吃掉。

2.2 逻辑推理

过桥问题

四个人，A、B、C 和 D，需要过一条河。唯一的过河方式是通过一座旧桥，这座桥一次最多只能容纳两个人。由于天色很暗，没有手电筒他们无法过桥，而他们只有一个手电筒。因此，每一对过桥的人必须以较慢者的速度行走。他们需要尽快让所有人都过到对岸去。A 最慢，过桥需要 10 分钟；B 需要 5 分钟；C 需要 2 分钟；D 需要 1 分钟。 将所有四个人都送到对岸所需的最短时间是多少？1脚注 1提示： 关键是要意识到 A 和 B 应该一起过桥。

补充说明： 这是经典的“过桥问题”。核心挑战在于如何让最慢的两个人一起过桥，同时避免让快的人白白浪费时间去来回护送他们。常见的错误是让 A 和 D 先过，这样会浪费大量时间。

解法： 关键点是要意识到，10 分钟的人应该和 5 分钟的人一起过桥，而且这不应该发生在第一次过桥时，否则他们中的一个必须折返。所以，C 和 D 应该先过河（花费 2 分钟）；然后让 D 返回（花费 1 分钟）；接着 A 和 B 一起过河（花费 10 分钟）；再让 C 返回（花费 2 分钟）；最后由 C 和 D 再次一起过河（花费 2 分钟）。 整个过程总共需要 17 分钟。或者，也可以在第二趟时先让 C 返回，然后让 D 返回，同样需要 17 分钟。具体步骤总结如下：

1. C 和 D 过桥 (2 分钟) -> 对岸有 C, D；这边有 A, B
2. D 返回 (1 分钟) -> 对岸有 C；这边有 A, B, D
3. A 和 B 过桥 (10 分钟) -> 对岸有 A, B, C；这边有 D
4. C 返回 (2 分钟) -> 对岸有 A, B；这边有 C, D
5. C 和 D 过桥 (2 分钟) -> 全部到达对岸

总计：2 + 1 + 10 + 2 + 2 = 17 分钟。

生日问题

你和你的同事们知道你们的上司 A 的生日是以下 10 个日期之一： 3月4日, 3月5日, 3月8日 6月4日, 6月7日 9月1日, 9月5日 12月1日, 12月2日, 12月8日 A 只告诉了你他生日的月份，只告诉你的同事 C 他生日的日子。之后，你首先说：“我不知道 A 的生日；C 也不知道。”在听到

查看本页原始扫描图

你这么说之后，C 回答：“我不知道 A 的生日，但现在我知道了。”你笑了，说：“我现在也知道了。”在看了这 10 个日期并听了你们的评论后，你们的行政助理在没有问任何问题的情况下写下了 A 的生日。那么助理写了什么？ 解法： 不要让“他说，她说”的部分迷惑你。只需解读每个人评论背后的逻辑，并尽力从这些评论中推导出有用的信息。

1. 建立初始知识:

你（Y）知道月份（M）；同事 C 知道日子（D）。所有可能的日期为 $D \in \{1, 2, 4, 5, 7, 8\}$。

1. 第一句话：你说的“我不知道；C 也不知道。”

• 如果生日是唯一的日期（即该日子只在列表中出现一次），C 会立即知道 A 的生日。在可能的 D 中，2 和 7 是唯一的日期（12月2日和6月7日）。
• 既然你确定 C 不知道，你就必须推断 C 被告知的日期 不是 2 或 7。
• 如果 C 被告知的日期是 2 或 7，那么 C 有可能一开始就知道生日。而你只有在知道 C 绝对不可能知道时才能说出这句话。这要求你知道的月份里不包含任何唯一日期。6月包含 7，12月包含 2。
• 结论： 你告诉我们的月份不是六月或十二月。所以生日月份只能是 三月 或 九月。

> 补充说明： 这句话是整个推理的关键。它排除了包含独特日子的月份，因为如果你知道了六月或十二月，你就无法确定 C 是否有机会直接知道答案。

1. 第二句话：C 说“我不知道，但现在我知道了。”

• 现在 C 知道月份一定是三月或九月。他立即算出了 A 的生日，这意味着在这个新信息下，他已知的日子（D）在剩下的日期中是唯一的。
• 在剩下的日期（3月4日，3月5日，3月8日，9月1日，9月5日）中，日子 4、8、1 出现了1次，但日子 5 出现了两次（3月5日和9月5日）。如果 C 知道的日子是 5，他仍然无法区分是三月还是九月，所以不会知道。
• 结论： 日期不能是 5。生日必须是 3月4日、3月8日 或 9月1日。

1. 第三句话：你说的“我现在也知道了。”

• 在这三种可能性中，3月4日和 3月8日都是 三月 的日期。如果你知道的月份是三月，你仍然无法确定是哪一天。
• 既然你能从这三个选项中确定 A 的生日，说明你知道的月份只能是 九月（因为九月中只有 9月1日 这一个选项）。
• 结论： A 的生日一定是 9月1日。
• 因此，助理一定写了 9月1日。

纸牌游戏

一家赌场提供一种使用一副 52 张普通扑克牌的纸牌游戏。规则是每次翻开两张牌。对于每一对牌，如果都是黑色的，则归庄家；如果都是红色的，则归到你的牌堆；如果一张是黑色的，一张是红色的，则被丢弃。这个过程重复进行，直到你们两人将 52 张牌全部处理完毕。如果你的牌堆中的牌多于庄家，你赢 100 美元；否则（包括平局）你什么也得不到。赌场允许你协商你愿意为这场游戏支付的价格。你愿意支付多少钱来玩这场游戏？解法： 这绝对是一家阴险的赌场。无论牌如何排列，最终你和庄家牌堆中的牌数量 总是相等。为什么？

因为每对丢弃的牌（红黑）都包含一张黑牌和一张红牌，所以 2脚注 2提示： 尝试使用对称性来解决问题。每对丢弃的牌都有一张黑牌和一张红牌。这告诉你剩余两堆牌中黑牌和红牌的数量有什么关系？

查看本页原始扫描图

到你的牌堆或庄家的牌堆的牌都是同色的。

补充说明： 我们可以这样理解：初始状态是 26 张红牌和 26 张黑牌。

每一轮游戏，我们都会翻开两张牌。有三种可能的结果：

1. 两张红牌： 这两张红牌进入你的牌堆。这意味着总红牌数减少 2，总黑牌数不变。

2. 两张黑牌： 这两张黑牌进入庄家的牌堆。这意味着总黑牌数减少 2，总红牌数不变。

3. 一张红一张黑： 这一红一黑被同时丢弃。这意味着总红牌数和总黑牌数各减少 1。

因为游戏开始时红牌和黑牌数量相等（都是 26），而且在任何一次操作中，被分配到你牌堆、庄家牌堆或丢弃区的红牌和黑牌数量总是相同，所以最终进入你牌堆的牌和进入庄家牌堆的牌的数量必定相等。具体来说，在你的牌堆中，红牌的数量等于庄家牌堆中黑牌的数量；你的牌堆中黑牌的数量等于庄家牌堆中红牌的数量。

所以，无论怎样玩，你和庄家最后牌堆里的牌数都是 26 张。结果只能是平局。既然你只有在你的牌多于庄家时才能赢钱，而平局时一无所得，那么你从这场游戏中 绝对无法赚钱。 因此，你愿意为玩这场游戏支付的价格是 0 美元。任何正数的价格都只会让你必输无疑。 红色和黑色的牌被丢弃。结果，你剩下的红牌数量和庄家剩下的黑牌数量始终相同。庄家总是赢！所以我们不应该付任何钱来玩这个游戏。

烧绳子

你有两根绳子，每根绳子完全燃烧需要1小时。但是，每根绳子在不同位置的密度不同，因此无法保证绳子内不同部分燃烧所需的时间一致。你如何用这两根绳子测量出45分钟？ 解答： 这是一个经典的脑筋急转弯问题。对于一根需要 \(x\) 分钟烧完的绳子，如果你同时点燃绳子的两端，它需要 \(x/2\) 分钟烧完。所以我们应该同时点燃第一根绳子的两端，同时点燃第二根绳子的一端。30分钟后，第一根绳子完全烧尽，而此时第二根绳子变成了一根需要30分钟烧完的绳子。此时，我们可以点燃第二根绳子的另一端（第一端仍在燃烧），当它烧尽时，总共经过的时间正好是45分钟。

有缺陷的球

你有12个完全相同的球。其中一个球比其他球重或轻（你不知道是哪个）。你只有一个天平，它只能显示哪一侧的托盘更重。你如何在3次测量内确定哪个球是有缺陷的？解答： 这个称重问题是另一个经典的脑筋急转弯，至今仍被许多面试官问及。球的总数通常在8到100多个之间。这里我们用 \(n=12\) 来展示基本方法。关键在于将原始组（以及任何中间子组）分成三组，而不是两组。原因是前两组的比较总能提供关于第三组的信息。考虑到解释起来文字较多，我在图2.1中画了一个树状图来详细展示方法。将球编号为1到12，并将它们分成三组，每组4个球。先将球1、2、3、4与球5、6、7、8称重。然后我们接着探讨两种可能的情况：两组平衡，用“=”号表示；或者组1、2、3、4比5、6、7、8轻，用“<”号表示。不需要解释1、2、3、4比5、6、7、8重的情况。（为什么？

4脚注 4这里是运用对称性思想的地方。标签1、2、3、4或5、6、7、8并没有特殊性。如果1、2、3、4比5、6、7、8重，我们只需交换这两组的标签。这样我们就得到了1、2、3、4比5、6、7、8轻的情况。） 如果两组平衡，这立即告诉我们有缺陷的球在9、10、11和12中，并且它比其他球轻（L）或重（H）。然后我们从第3组取出9、10、11，并将球9、10与8、11进行比较。

这里我们已经知道8是一个正常球。如果9、10较轻，则意味着9或10是有缺陷的且为L，或者11是有缺陷的且为H。在这种情况下，我们只需比较9和10。如果9较轻，则9是有缺陷的且为L；如果9和10平衡，则11必定是有缺陷的且为H；如果9较重，则10是有缺陷的且为L。如果9、10和8、11平衡，则12是有缺陷的。如果9、10较重，则9或10是有缺陷的且为H，或者11是有缺陷的且为L。你可以轻松地按照图2.1中的树状图进行进一步分析，并且可以清楚地看出所有可能的情况都可以在3次测量中解决。

总的来说，如果你知道有缺陷的球是偏重还是偏轻，

查看本页原始扫描图

补充说明： 这里的思想是，每次称重结果（相等、左重、左轻）提供了三种可能，相当于一个三分支。使用 \(n\) 次称重，可以区分最多 \(3^n\) 种可能情况。如果知道缺陷球轻重，每个球只有一种缺陷状态（例如，12个球各有1种可能性），所以总共有12种情况，而 \(3^2=9<12\) 不够，\(3^3=27\) 足够，因此3次称重可行。如果不知道轻重，每个球有轻重两种可能，加上一个正常球，共有 \(2n+1\) 种情况，但 \(3^n\) 必须覆盖这些情况，最大 \(n\) 满足 \(3^n \geq 2n+1\)，对于 \(n=3\)，\(27 \geq 25\)，所以12个球可行。一般公式 \((3^n-3)/2\) 来源于此。

轻一些，你可以用不超过 \(n\) 次称重来识别出最多 \(3^n\) 个球中的有缺陷球，因为每次称重都能将问题规模缩小 \(2/3\)。如果你不知道有缺陷球是偏轻还是偏重，你最多可以用 \(n\) 次称重来识别出 \((3^n-3)/2\) 个球中的有缺陷球。

尾随零

100!（100的阶乘）有多少个尾随零？ 解答： 这是一个简单的问题。我们知道每对2和5会产生一个尾随零。如果我们对100!中的所有数字进行质因数分解，很明显数字2的频率远远超过数字5的频率。因此，数字5的频率决定了尾随零的数量。在数字1、2、...、99和100中，有20个数字能被5整除（5、10、...、100）。在这20个数字中，有4个数字能被 \(5^2\) 整除（25、50、75、100）。所以数字5的总频率是24，因此有24个尾随零。

赛马

有25匹马，每匹马都以不同于其他马的恒定速度奔跑。由于赛道只有5条车道，每场比赛最多可以有5匹马参加。如果你需要找出跑得最快的3匹马，最少需要多少场比赛来识别它们？解答： 这个问题考验你的基本分析能力。要找出跑得最快的3匹马，肯定需要测试所有马匹。因此，一个自然的步骤是将马匹分成5组（每组包含马匹1-5、6-10、11-15、16-20、21-25）。经过5场比赛后，我们将得到每组内部的排名。假设排名遵循数字顺序（例如，在6-10组中，6号马最快，10号马最慢）5脚注 5这样的假设不影响解决方案的普遍性。如果顺序不是如所述，只需更改马匹的标签即可。。

这意味着1号、6号、11号、16号和21号是各自组中最快的马。每组最后两名马匹肯定被淘汰。我们还能推断出什么？我们知道在每组中，如果最快的马在25匹马中排名第5或第4，那么该组的所有马匹都无法进入前3名；如果它排名第3，那么该组中没有其他马匹能进入前3名；如果它排名第2，那么该组中可能还有一匹马进入前3名；如果它排名第1，那么该组中可能有两匹马进入前3名。

查看本页原始扫描图

赛马问题

那么，我们来比赛1号、6号、11号、16号和21号马。同样，不失一般性，我们假设它们的顺序是1、6、11、16和21。那么我们立刻知道4-5号、8-10号、12-15号、16-20号和21-25号马被淘汰了。由于1号马是所有马中最快的，所以它肯定在。我们需要确定2号、3号、6号、7号和11号马中的哪两匹能进入前三名，这只需要再进行一场比赛。 所以，总共我们需要7场比赛（分3轮）来确定最快的3匹马。

无穷序列

如果 \(x^{x^{x^{x^{\dots}}}}=2\)，其中 \(x^y = x^y\)，那么 \(x\) 是多少？ 解答： 这个问题看起来很难，但简单的分析就能得到一个优雅的解法。从原方程中我们得到了什么？ \[ \lim_{n \to \infty} \underbrace{x^{x^{x^{\dots}}}_{n \text{ 项}}} = 2 \iff \lim_{n \to \infty} \underbrace{x^{x^{x^{\dots}}}}_{n-1 \text{ 项}} = 2 \] 换句话说，当 \(n \to \infty\) 时，增加或减少一个 \(x\) 的幂次应该产生相同的结果。 所以 \(x^{x^{x^{x^{\dots}}}}=x^{(x^{x^{x^{\dots}}}})\)。因此，我们可以写成 \(x^2 = 2\)，即 \(x = \sqrt{2}\)。

补充说明： 这个解法的核心是无穷幂塔的极限值对塔高不敏感。因为无限叠加上去，塔的最顶层多一个x或少一个x不会改变整个表达式的值。所以原表达式等于2，意味着加上一个x后，x的(原表达式)次方也等于2，即x^2=2。注意，这个推理假设极限存在，实际上当x=sqrt(2)时，极限确实收敛于2。

2.3 跳出思维定势

箱子打包

你能将53个尺寸为 \(1 \times 1 \times 4\) 的砖块打包到一个 \(6 \times 6 \times 6\) 的箱子里吗？解答： 这是一个从流行的国际象棋棋盘问题延伸出来的有趣问题。在那个问题中，你有一个 \(8 \times 8\) 的国际象棋棋盘，移除了两个位于对角线上的小方格。你有许多尺寸为 \(1 \times 2\) 的砖块。你能将31块砖块放入剩余的62个方格中吗？（一个替代问题是，你是否能用砖块覆盖所有62个方格，且砖块之间不重叠，也不超出棋盘范围，这需要类似的分析。） 一个真实的国际象棋棋盘图肯定有助于可视化。如图2.2所示，当一个国际象棋棋盘被填满交替的黑白方格时，位于对角线上的两个方格颜色相同。如果你将一块 \(1 \times 2\) 的砖块放在棋盘上，它总是会覆盖一个黑格和一个白格。

假设移除了两个黑色的对角方格，那么棋盘上剩余的方格最多只能容纳30块砖块，因为我们只剩下30个黑格（每块砖块需要一个黑格）。因此，打包31块砖块是不可能的。要覆盖所有62个方格而不重叠或超出范围，我们必须正好使用31块砖块。然而，我们已经证明了31块砖块无法做到。

查看本页原始扫描图

装入剩余的62个方格中，所以你无法找到一种方法在不重叠或超出范围的情况下填满所有62个方格。

就像任何好的交易策略一样，如果越来越多的人知道并复制它，这种策略的有效性就会消失。随着棋盘问题变得流行，许多面试者只是记住了答案（毕竟，记住答案很容易）。所以一些富有创意的面试官想出了更新的版本来测试你的思考过程，或者至少测试你将知识扩展到新问题的能力。如果我们观察这个三维问题的总体积，53块砖的体积是212，小于盒子的体积216。然而，我们可以用类似棋盘问题的方法证明，不可能将所有砖块都装入盒子。让我们想象一下，这个6×6×6的盒子实际上是由小的2×2×2立方体组成的。应该有27个小立方体。类似于棋盘问题（但在三维中），想象我们有黑色立方体和白色立方体交替排列——这确实需要一点三维想象力。因此，我们可能有14个黑色立方体和13个白色立方体，或者13个黑色立方体和14个白色立方体。对于任何一块我们装入盒子的1×1×4砖块，它的一半（1×1×2）必须位于一个黑色的2×2×2立方体中，而另一半必须位于一个白色的2×2×2立方体中。

问题在于，每个2×2×2立方体最多只能被4块1×1×4砖块使用。因此，对于有13个立方体的那种颜色（无论是黑色还是白色），我们最多只能将它们用于52个1×1×4砖块。没有办法放置第53块砖。所以，我们无法将53块尺寸为1×1×4的砖块装入一个6×6×6的盒子中。

日历骰子

你刚刚定制了两个骰子。骰子的每个面上不是数字1-6，而是放置了单个数字，这样你每天早晨都可以排列骰子，使两个骰子的正面显示当天的日期。你必须使用两个骰子（换句话说，日期1-9必须显示为01-09），但你可以交换骰子的位置。

补充说明： 这意味着对于个位数日期，我们需要用两个骰子组合出“0X”的形式，例如“01”表示1号。

你想怎样排列骰子上的数字，才能让这两个骰子上的数字组合起来，可以表示出一年中的所有日期？ 解答： 一个月中的日期包含11号和22号，所以两个骰子都必须有数字1和2。为了表示个位数日期，我们至少需要一个骰子上有0。我们先在第一个骰子上放一个0。考虑到我们需要表示所有个位数日期，并且第二个骰子不能包含1-9的所有数字，因此为了表示所有个位数日期，第二个骰子也必须有一个0。 到目前为止，我们已经分配了以下数字：

如果我们能将剩余的数字3, 4, 5, 6, 7, 8, 和9分配到剩余的面，问题就解决了。但是还有7个数字。我们该怎么办？这时你需要跳出思维定势。我们可以将6当作9来使用，因为它们不会同时被需要！所以，只需将3, 4, 和5放在一个骰子上，将6, 7, 和8放在另一个骰子上，那么这两个骰子上的最终数字是：

补充说明： 这里“6”可以旋转180度当作“9”使用，所以骰子二上的6/7/8实际上可以表示6, 7, 8, 9四个数字，从而覆盖所有日期。

通往机会之门

你面前有两扇门。一扇通往你的工作机会，另一扇通往出口。每扇门前都站着一个守卫。一个守卫总是说谎，另一个总是说真话。你只能问一个守卫一个是/否问题。假设你确实想得到工作机会，你会问什么问题？ 解答： 这是另一个经典的脑筋急转弯（在我看来可能有点过时了）。一个流行的答案是问一个守卫：“另一个守卫会说你正在看守机会之门吗？”如果他回答“是”，就选择另一扇门；如果他回答“否”，就选择这个守卫站的那扇门。 有两种可能的情况：

1. 说真话的守卫看守机会之门；说谎的守卫看守出口之门。
2. 说真话的守卫看守出口之门；说谎的守卫看守机会之门。

如果我们问一个守卫一个直接的问题，例如“你正在看守机会之门吗？”对于情况1，两个守卫都会回答“是”；对于情况2，两个守卫都会回答“否”。所以一个直接提问无助于我们解决问题。关键在于像流行的答案那样，让两位守卫都参与到提问中。对于场景1，如果我们碰巧选择了说真话的守卫，他会回答“否”，因为说谎的守卫会说“否”；如果我们碰巧选择了说谎的守卫，他会回答“是”，因为说真话的守卫会说“否”。对于场景2，如果我们碰巧选择了说真话的守卫，他会回答“是”，因为说谎的守卫会说“是”；如果我们碰巧选择了说谎的守卫，他会回答“否”，因为说真话的守卫会说“是”。因此，对于这两种场景，如果答案是“否”，我们就选择那个门；如果答案是“是”，我们就选择另一个门。

信息传递

你需要通过一个信使服务与你在格林威治的同事沟通。你的文件被装在一个带锁的盒子里寄送。不幸的是，信使服务并不安全，所以任何放在未上锁盒子里的东西（包括你放在盒子里的任何锁）在递送过程中都会丢失。你和你的同事各自使用的这种高安全性挂锁都只有一把钥匙，而持有钥匙的是上锁的人。你如何才能安全地将文件发送给你的同事？ 解答： 如果你要递送一份文件，显然你不能把它放在一个未上锁的盒子里。所以第一步是把它锁在一个盒子里寄往格林威治。由于你持有这把锁的钥匙，你的同事无法打开盒子拿到文件。你必须以某种方式在他拿到文件之前移除锁，这意味着在你的同事拿到文件之前，盒子应该被送回到你这里。 那么，在他把盒子寄回来之前，他能做什么呢？他可以在盒子上再加一把锁，这把锁的钥匙在他那里！一旦盒子回到你手中，你就会解开你自己的锁，然后把盒子寄回给你的同事。他会解开他自己的锁，拿到文件。

最后一颗球

一个袋子里有20个蓝球和14个红球。每次你随机取出两个球。（假设袋子里的每个球被取出的概率相等）。你不会把这两个球放回。相反，如果两个球颜色相同，你就往袋子里加一个蓝球；如果颜色不同，你就往袋子里加一个红球。假设你有无限的蓝球和红球供应，如果你不断重复这个过程，袋子里最后剩下的球会是什么颜色？如果袋子里有20个蓝球和13个红球呢？6脚注 6提示：你可以在盒子上放不止一把锁。 7脚注 7提示：考虑每一步之后红球和蓝球数量的变化。 解答： 一旦你理解了提示，这个问题应该很简单。用$(B, R)$表示袋中蓝球和红球的数量。我们可以看看取出两个球后会发生什么。

两个都是蓝球：$(B, R) \rightarrow (B-1, R)$ 两个都是红球：$(B, R) \rightarrow (B+1, R-2)$ 一个红球一个蓝球：$(B, R) \rightarrow (B-1, R)$ 注意，$R$要么保持不变，要么减少2，所以如果我们从14个红球开始，红球的数量永远不会变成奇数。我们还知道，每次操作后球的总数减少一个，直到只剩下一个球。结合我们已有的信息，最后一个球一定是蓝球。类似地，当我们从奇数个红球开始时，最后一个球一定是红球。

电灯开关

房间里有一个灯泡，外面有四个开关。所有开关目前都处于关闭状态，并且只有一个开关控制灯泡。你可以随意打开或关闭任意数量的开关任意次数。你需要进入房间多少次才能找出哪个开关控制灯泡？解答： 你可能见过这个问题的经典版本：房间里有3个灯泡，外面有3个开关。虽然这个问题略有改动，但方法完全相同。灯泡的亮与灭是二元的，这只能让我们区分两个开关。如果我们有另一个二元因素，就有$2 \times 2 = 4$种可能的场景组合，这样我们就能区分4个开关。除了光，灯泡还会发热，点亮一段时间后会变热。所以我们可以利用亮/灭和冷/热的组合来决定四个开关中哪一个控制灯泡。打开开关1和2；继续解决其他谜题或做任何你喜欢的事情一段时间；关闭开关2并打开开关3；快速进入房间，触摸灯泡并观察它是亮还是灭。灯泡亮且热 $\rightarrow$ 开关1控制灯泡；灯泡灭且热 $\rightarrow$ 开关2控制灯泡；

灯泡亮且冷 $\rightarrow$ 开关3控制灯泡；灯泡灭且冷 $\rightarrow$ 开关4控制灯泡。来自不同银行的八位量化分析师聚在一起喝酒。他们都想知道这个群体的平均薪资。然而，作为谨慎且谦逊的人，每个人都更倾向于不向群体透露自己的薪资。你能想出一个策略，让量化分析师们在不知道彼此薪资的情况下计算出平均薪资吗？解答： 这是一个轻松的问题，答案不止一个。一种方法是：第一位量化分析师选择一个随机数，将其加到自己的薪资上，然后把结果交给第二位量化分析师。第二位量化分析师将自己的薪资加到结果上，再交给第三位；……；第八位量化分析师将自己的薪资加到结果上，然后交回给第一位量化分析师。接着，第一位量化分析师从总和中减去那个“随机”数，再将“真实”总和除以 8，就得到了平均薪资。你可能会想，这个策略除了作为考验面试官的脑筋急转弯外，是否还有其他用处？实际上它确实有应用。

例如，第三方数据提供商从所有参与公司收集基金持仓数据（基金持有的证券及其股数），然后将信息分发给参与者。当然，大多数参与者不希望别人弄清楚他们持有什么。如果基金中的每个持仓每天都有相同的基金 ID，那么很容易从持仓中逆向推导出基金并复制其策略。因此，在分发之前，数据提供商会向基金中每个持仓的基金 ID 添加不同的随机数（更确切地说是伪随机数，因为提供商知道每个持仓的基金 ID 加了什么数，并且使用了复杂的算法来确保映射是一一对应的）。这样一来，同一基金中的持仓看起来就有了不同的基金 ID。这可以防止参与者重构其他基金。通过这种方法，参与者可以共享市场信息，同时保持匿名。

2.4 对称性的应用

硬币堆问题

假设你被蒙住眼睛在一个房间里，并被告知地上有 1000 枚硬币。其中 980 枚硬币正面朝下（反面），另外 20 枚硬币正面朝上（正面）。你能将这些硬币分成两堆，以保证两堆中正面朝上的硬币数量相等吗？假设你无法通过触摸来判断硬币的正反面，但你可以翻转任意数量的硬币。解答： 假设我们将 1000 枚硬币分成两堆，一堆有 $n$ 枚硬币，另一堆有 $1000-n$ 枚硬币。如果第一堆中有 $m$ 枚硬币正面朝上，那么第二堆中正面朝上的硬币数必定是 $20-m$ 枚。我们还知道第一堆中有 $n-m$ 枚硬币正面朝下。显然，仅通过调整 $n$ 无法保证 $m=10$。我们还有什么其他选择？我们可以翻转硬币。既然我们无法知道硬币的正反面，有选择地翻转硬币并不能保证任何结果。但是，如果我们翻转第一堆中的所有硬币，那么所有正面会变成反面，所有反面会变成正面。结果，第一堆中将有 $n-m$ 枚正面朝上和 $m$ 枚正面朝下（对称性）。

因此，我们需要让原始第一堆中反面的数量等于第二堆中正面的数量；换句话说，让 $n-m = 20-m$。$n=20$ 能使等式成立。如果我们随机取出 20 枚硬币并将它们全部翻转，那么这 20 枚被翻转的硬币中正面朝上的数量，应该与另外 980 枚硬币中正面朝上的数量相同。

补充说明： 这个策略的关键在于利用了“翻转所有硬币”这一操作，它改变了第一堆中正反面的构成，使其与第二堆的正面数量建立联系。通过巧妙设定第一堆的硬币数（20枚），并全部翻转，就能保证两堆的正面数相等。

标签错误的袋子

你有三个装有水果的袋子。一个袋子只装苹果；一个袋子只装橙子；一个袋子混合装有苹果和橙子。每个袋子上都贴有一个标签（苹果、橙子或混合）。不幸的是，你的经理告诉你所有袋子的标签都是错的。请设计一个策略，通过取出最少数量的水果来识别每个袋子？你可以从任何袋子中取出任意数量的水果。⁸ 解答： 这里的关键是利用所有袋子标签都错误这一事实。例如，贴有“苹果”标签的袋子，里面装的要么全是橙子，要么是苹果和橙子的混合物。我们来看看标签：橙子、苹果、混合（橙子+苹果）。你是否意识到“橙子”标签和“苹果”标签是对称的？如果没有，让我详细解释一下：如果你从贴有“橙子”标签的袋子里取出一个水果，结果是苹果（橙子标签 → 苹果），那么这个袋子要么全是苹果，要么是混合的。如果你从贴有“苹果”标签的袋子里取出一个水果，结果是橙子（苹果标签 → 橙子），那么这个袋子要么全是橙子，要么是混合的。

对称的标签并不令人兴奋，很可能不是正确的切入点。所以，让我们尝试从贴有“混合”标签的袋子里取出一个水果。如果我们取出的水果是橙子，那么我们就知道这个袋子实际上是橙子袋（它不可能是苹果和橙子的混合物，因为我们知道袋子的标签是错的）。既然贴有“苹果”标签的袋子不可能只装苹果，那么它一定是混合袋。而贴有“橙子”标签的袋子一定是苹果袋。类似地，如果从“混合”标签袋子里取出的是苹果，我们同样可以通过一次取水果来确定所有袋子。

• 我第一次看到这个问题时，觉得它像是一个文字游戏。但它确实能测试候选人的逻辑推理能力以及对细节的关注。

查看本页原始扫描图

智者问题

一位苏丹抓获了 50 位智者。他有一个玻璃杯，目前底部朝下放置。每分钟，他会随机叫一位智者，这位智者可以选择将玻璃杯翻转（使其底部朝上或底部朝下），或者什么都不做。智者们会被随机叫到，可能被叫到无限次。当有人被叫到并正确地声明所有智者都至少被叫到过一次时，所有人都可以获得自由。但如果他的声明是错误的，苏丹就会处死所有人。智者们在被分别关进独立的房间（每人一个房间）之前，只允许沟通一次。请设计一个策略，让智者们能够获得自由。解答： 为了使策略奏效，需要有一位智者，我们称他为发言人，来声明所有人都已被叫到。这告诉我们什么？1. 其他 49 位智者是等价的（对称的）。2. 发言人与其他 49 位智者不同。因此，自然而然地，这 49 位等价的智者应该采取相同的行动，而发言人应该采取不同的行动。以下是一种这样的策略：49 位（等价的）智者中的每一位，在第一次看到玻璃杯底部朝下时，都将其翻转。

如果玻璃杯已经底部朝上，或者他已经翻转过一次玻璃杯，则什么都不做。发言人应该在每次看到玻璃杯底部朝上时将其翻转到底部朝下，如果玻璃杯已经底部朝下，则什么都不做。在他完成第 49 次翻转后，这意味着其他 49 位智者都已被叫到，他就可以声明所有智者都已被叫到。

补充说明： 这个策略的核心是让玻璃杯的状态（朝上或朝下）作为一个计数器。发言人的翻转动作（将朝上翻转为朝下）记录了他看到其他智者“首次被叫到并翻转杯子”的次数。当这个计数达到 49 时，就说明所有其他智者都至少被叫到过一次。

2.5 数列求和

这是一个关于传奇数学家/物理学家高斯（Gauss）的著名故事：当他还是个孩子时，他的老师布置了一项枯燥的任务，要求孩子们计算从 1 加到 100 的和。令老师惊讶的是，高斯不到一分钟就交出了答案。这是他的方法： \[ \sum_{n=1}^{100} n = 1 + 2 + \dots + 99 + 100 \] \[ \sum_{n=1}^{100} n = 100 + 99 + \dots + 2 + 1 \] 将这两个等式相加，得到： \[ 2 \sum_{n=1}^{100} n = (1+100) + (2+99) + \dots + (99+2) + (100+1) = 101 + 101 + \dots + 101 + 101 = 101 \times 100 \] 因此， \[ \sum_{n=1}^{100} n = \frac{100 \times 101}{2} \]

查看本页原始扫描图

这种方法可以推广到任意整数 \(N\)： \[ \sum_{n=1}^{N} n = \frac{N(N+1)}{2} \] 连续平方数的求和公式可能不那么直观： \[ \sum_{n=1}^{N} n^2 = \frac{N(N+1)(2N+1)}{6} = \frac{N^3}{3} + \frac{N^2}{2} + \frac{N}{6} \] 但如果我们能猜出 \( \sum_{n=1}^{N} n^2 = aN^3 + bN^2 + cN + d \) 的形式并代入初始条件： \[ \begin{aligned} N=0 &\Rightarrow 0 = d \\ N=1 &\Rightarrow 1 = a+b+c+d \\ N=2 &\Rightarrow 5 = 8a+4b+2c+d \\ N=3 &\Rightarrow 14 = 27a+9b+3c+d \end{aligned} \] 就会得到解 \(a = 1/3, b = 1/2, c = 1/6, d = 0\)。

然后我们就能用数学归纳法轻易证明，这个公式对所有 \(N\) 都成立。

钟表碎片

一个钟表（数字按顺时针方向从 1 标到 12）从墙上掉下来，摔成了三块。你发现每块碎片上的数字之和都相等。每块碎片上分别是哪些数字？（不允许出现形状奇特的碎片。） 解：利用求和公式，\( \sum_{n=1}^{12} n = \frac{12 \times 13}{2} = 78 \)。因此每块碎片上的数字之和必须等于 26。有些面试者会错误地认为，因为不允许出现形状奇特的碎片，所以每块碎片上的数字必须是连续的。很容易发现 5、6、7、8 加起来等于 26。那么这些面试者的思路就卡住了，因为他们找不到更多连续的数字，使其和也为 26。 这个假设是不正确的，因为在钟表上，12 和 1 是连续的。一旦排除了这个错误假设，问题就变得清晰了：12+1=13，11+2=13。所以第二块碎片包含 11、12、1 和 2；第三块碎片包含 3、4、9 和 10。

缺失的整数

假设我们有 98 个不同的整数，它们来自 1 到 100。找出两个缺失的整数（在[1, 100]内）的好方法是什么？

查看本页原始扫描图

答案

解： 将缺失的整数表示为 \(x\) 和 \(y\)，现有的整数表示为 \(z_1, \dots, z_{98}\)。应用求和公式，我们得到： \[ \sum_{n=1}^{100} n = x + y + \sum_{i=1}^{98} z_i \Rightarrow x + y = \frac{100 \times 101}{2} - \sum_{i=1}^{98} z_i \] \[ \sum_{n=1}^{100} n^2 = x^2 + y^2 + \sum_{i=1}^{98} z_i^2 \Rightarrow x^2 + y^2 = \frac{100^3}{3} + \frac{100^2}{2} + \frac{100}{6} - \sum_{i=1}^{98} z_i^2 \] 利用这两个方程，我们可以轻松求解 \(x\) 和 \(y\)。

如果你使用计算机程序来实现这个策略，那么对于 \(1\) 到 \(n\) 中的两个缺失整数，该算法的复杂度显然是 \(O(n)\)。

假币 I

有 10 袋硬币，每袋有 100 枚相同的硬币。除一袋外，所有袋子里的硬币每枚重 10 克。然而，假币袋里的所有硬币每枚重 9 克或 11 克。你能只用一次称量，使用能显示确切重量的电子秤，找出假币袋吗？ 解： 是的，我们可以在一次称量中找出假币袋。从第一个袋子里取出 1 枚硬币，从第二个袋子里取出 2 枚，从第三个袋子里取出 3 枚，……，从第十个袋子里取出 10 枚硬币。总共有 \(\sum_{i=1}^{10} n = 55\) 枚硬币。如果没有假币，它们应该重 550 克。假设第 \(i\) 袋是假币袋，那么会有 \(i\) 枚假币，所以最终重量将是 \(550 \pm i\)。由于 \(i\) 对每个袋子都是唯一的，我们可以通过 \(550 \pm i\) 来识别假币袋以及假币是比真币轻还是重。 这并非唯一的答案：我们可以从每个袋子里选择不同数量的硬币，只要它们数量都不同即可。

玻璃球

你手里拿着两个玻璃球，在一个 100 层楼的建筑里。如果一个球从窗户扔出去，当楼层数小于 \(X\) 时它不会碎，而当楼层数大于或等于 \(X\) 时它一定会碎。 <p>⁹ 提示：为了在一次称量中找出假币袋，从每个袋子里取出的硬币数量必须不同。如果我们从两个袋子里取出相同数量的硬币，那么如果其中一个袋子是假币袋，对称性将阻止你区分这两个袋子。</p>

查看本页原始扫描图

楼层数等于或大于 \(X\)。你想确定 \(X\)。在最坏情况下，哪种策略可以使投掷次数最少？10脚注 10提示： 假设我们设计一个最多投掷 \(N\) 次的策略。如果第一个球投掷一次，第二个球可以覆盖 \(N-1\) 层；如果第一个球投掷两次，第二个球可以覆盖 \(N-2\) 层…… 解：假设我们有一个最多投掷 \(N\) 次的策略。对于第一个球的第一次投掷，我们可以尝试第 \(N\) 层。

如果球碎了，我们可以从第一层开始尝试第二个球，然后逐层增加楼层数，直到第二个球也碎了。最多需要测试 \(N-1\) 层。因此，最多 \(N\) 次投掷足以覆盖所有可能性。如果从第 \(N\) 层投出的第一个球没有碎，我们还剩下 \(N-1\) 次投掷机会。这次，我们只能将第一个球的楼层数增加 \(N-1\)，因为如果第一个球碎了，第二个球最多只能覆盖 \(N-2\) 层。如果从第 \((2N-1)\) 层投出的第一个球没有碎，我们还剩下 \(N-2\) 次投掷机会。因此，我们只能将第一个球的楼层数增加 \(N-2\)，因为如果第一个球碎了，第二个球最多只能覆盖 \(N-3\) 层…… 利用这种逻辑，我们可以看到，使用最多 \(N\) 次投掷，这两个球可以覆盖的楼层数是 \(N + (N-1) + \dots + 1 = \frac{N(N+1)}{2}\)。

为了覆盖 100 层，我们需要 \(\frac{N(N+1)}{2} \ge 100\)。取最小整数，我们得到 \(N=14\)。基本上，我们从第 14 层开始投掷第一个球。如果球碎了，我们可以用第二个球尝试第 1, 2, ..., 13 层，最多投掷 14 次（当第 13 层或第 14 层是 \(X\) 时）。如果第一个球没有碎，我们将尝试从第 \(14 + (14-1) = 27\) 层投掷第一个球。如果它碎了，我们可以用第二个球覆盖第 15, 16, ..., 26 层，总共最多投掷 14 次……

补充说明： 这里的核心思想是，第一次投掷的策略要平衡最坏情况下的总投掷次数。如果第一次投掷的楼层太高，第一个球可能很快碎掉，那么第二个球就需要逐层测试很多楼层；如果第一次投掷的楼层太低，第一个球可能不会碎，但会消耗掉一次投掷机会，后续的测试空间也会被压缩。所以，我们让每次投掷的楼层间隔逐次减少 1，这样无论第一个球在哪次投掷后碎掉，剩下的投掷次数都刚好能确保第二个球逐层测试完所有可能的楼层，从而保证最坏情况下的总投掷次数相同且最小。

2.6 鸽巢原理

鸽巢原理的基本版本是：如果你拥有的鸽巢比鸽子少，并且你将每只鸽子都放入一个鸽巢，那么至少有一个鸽巢里有多于一只鸽子。基本上，它说明如果你有 \(n\) 个鸽巢和多于 \(n+1\) 只鸽子，那么至少有 2 只鸽子必须共享一个鸽巢。推广版本是：如果你有 \(n\) 个鸽巢和至少 \(mn+1\) 只鸽子，那么至少有 \(m+1\) 只鸽子必须共享一个鸽巢。这些简单直观的想法在许多问题中都非常有用。这里我们将通过一些例子来展示它们的应用。

查看本页原始扫描图

配袜子

你的抽屉里有 2 只红袜子、20 只黄袜子和 31 只蓝袜子。作为一个忙碌且心不在焉的麻省理工学院学生，你只是随机从抽屉里抓出一些袜子，试图找到一双颜色相同的袜子。假设每只袜子被选中的概率相等，为确保得到一双颜色相同的袜子，你至少需要抓出多少只袜子？ 解：这个问题只是双色袜子问题（此时你只需要 3 只袜子）的一个变体。当你有 3 种颜色（3 个鸽巢）时，根据鸽巢原理，你需要 \(3+1=4\) 只袜子（4 只鸽子）来保证至少有两只袜子颜色相同（2 只鸽子共享一个巢）。

握手

你被邀请参加一个欢迎派对，同行的有 25 名团队成员。每位团队成员都与你握手表示欢迎。由于房间里很多人彼此之间并不认识，其他人之间也发生了很多随机的握手。如果你不知道握手的总次数，你能肯定地说，在场至少有两个人和同样数量的人握过手吗？ 解：派对上有 26 个人，每个人握手的次数在 1 次到 25 次之间——因为每个人至少都和你握过一次手。换句话说，有 26 只鸽子和 25 个鸽巢。因此，至少有两个人和恰好同样数量的人握过手。

我们以前见过吗？

证明：如果派对上有 6 个人，那么要么至少有 3 个人在派对前彼此认识，要么至少有 3 个人在派对前互不相识。 解：这个问题看起来很复杂，面试者常常对面试官到底想问什么感到困惑。但一旦你开始分析可能的情况，答案就变得显而易见了。 假设你是派对上的第 6 个人。那么根据推广的鸽巢原理（对于如此直观的结论，我们甚至需要用这个原理吗？），在剩下的 5 个人中，我们可以得出：要么至少有 3 个人认识你，要么至少有 3 个人不认识你。现在我们来探讨这两个互斥且完备的场景： 情形 1：假设至少有 3 个人之前认识你。

查看本页原始扫描图

如果这群人中恰好有两个人互相认识，那么你和那两个人（总共 3 个人）就彼此认识。如果这群人中没有任何两个人互相认识，那么这群人（至少 3 个人）就彼此都不认识。无论哪种子情形，结论都成立。 情形 2：假设至少有 3 个人之前不认识你。 如果这群人中恰好有两个人互相不认识，那么你和那两个人（总共 3 个人）就彼此都不认识。如果这群人中所有对人都彼此认识，那么这群人（至少 3 个人）就互相认识。同样，无论哪种子情形，结论都成立。

正方形上的蚂蚁

在一个边长为 1 的正方形上有 51 只蚂蚁。如果你有一个半径为 1/7 的玻璃杯，你能保证将杯子放在正方形上的某个位置，使得杯子至少罩住 3 只蚂蚁吗？11脚注 11提示：将正方形划分为 25 个更小的区域；那么至少有一个区域包含 3 只蚂蚁。 解答： 要确保玻璃杯能罩住至少 3 只蚂蚁，我们可以将正方形划分为 25 个更小的区域。应用广义鸽巢原理可知，至少有一个区域包含至少 3 只蚂蚁。因此，我们只需确保玻璃杯足够大，能覆盖这 25 个小区域中的任意一个。

只需将正方形划分为 5×5 个边长为 1/5 的小正方形即可，因为半径为 1/7 的圆可以覆盖边长为 1/5 的正方形12脚注 12半径为 $r$ 的圆可以覆盖边长最大为 $\sqrt{2}r$ 的正方形，且 $\sqrt{2} \approx 1.414$。。

假币问题 II

有 5 个袋子，每个袋子里装有 100 枚硬币。一枚硬币的重量可能是 9 克、10 克或 11 克。每个袋子里的硬币重量相同，但我们不知道每个袋子装的是哪种硬币。你有一台电子秤（可以显示精确重量）。你需要使用多少次秤，才能确定每个袋子装的是哪种硬币？13脚注 13提示：从一个更简单的问题开始。如果你只有两个袋子而不是 5 个，你需要从每个袋子中取出多少枚硬币才能确定任一袋子的硬币类型？硬币数量的最小差异是多少？那么三个袋子呢？ 解答： 如果 5 个袋子的答案不明显，让我们从问题的最简版本开始——1 个袋子。

我们只需要取出一枚硬币称重即可。现在考虑 2 个袋子的情况。为了确定袋子 1 和袋子 2 的硬币类型，我们需要从袋子 2 中取出多少枚硬币？考虑到袋子 1 有三种可能的类型，我们需要从袋子 2 中取出 3 枚硬币；2 枚硬币是不够的。为了简化标记，我们将三种类型的重量值改为 -1、0 和 1（减去均值 10）。如果

查看本页原始扫描图

我们只从第二个袋子中取出 2 枚硬币，那么第一个袋子的 1 枚硬币与第二个袋子的 2 枚硬币的总和范围是 -3 到 3（共 7 个可能的和值，即 7 个“鸽巢”）。同时，我们有 9 种（3×3）可能的组合来表示两个袋子中硬币的重量（即 9 只“鸽子”）。因此，至少有两种组合会产生相同的总和（因为 9 > 7，至少两只鸽子必须进入同一个鸽巢），我们将无法区分它们。如果我们从第二个袋子中取出 3 枚硬币，那么总和范围是 -4 到 4，这足以覆盖所有 9 种组合。下表精确地显示了所有可能的组合都会产生不同的总和：

C1 和 C2 分别代表来自袋子 1 和袋子 2 的硬币的重量。

补充说明： 这里 C1 和 C2 是每个袋子中单枚硬币的重量类型（-1、0 或 1）。表格中的每个单元格是“1 × C1 + 3 × C2”的结果。可以看到，所有 9 个结果都不同，因此根据称出的总重量，我们可以唯一地反推出 C1 和 C2 的值。

那么 3 个袋子呢？我们将有 $3^3 = 27$ 种可能的组合。一个范围从 -13 到 13 的指示值肯定可以覆盖它，这意味着我们需要从第三个袋子中取出 9 枚硬币。可能的组合如下表所示：

C1、C2 和 C3 分别代表来自袋子 1、2 和 3 的硬币的重量。

补充说明： 此处的总和公式为“1 × C1 + 3 × C2 + 9 × C3”。通过为每个袋子分配不同的权重（1, 3, 9），我们确保了所有 27 种组合的总和互不相同。这是一种基于加权和或进制表示的思想。

遵循这个逻辑，我们可以很容易地看到，对于第四个袋子，我们需要取出 27 枚硬币，对于第五个袋子，需要取出 81 枚硬币。因此，答案是：分别从袋子 1、2、3、4 和 5 中取出 1、3、9、27 和 81 枚硬币，然后进行一次称重，即可根据总重量唯一地确定每个袋子包含的硬币类型。

2.7 模运算

模运算——表示为 x % y 或 x mod y——用于求数字 x 除以另一个数字 y 的余数。为简化起见，我们只考虑 y 是正整数的情况。例如，5 % 3 = 2。模运算的一个直观性质是：如果 $x_1 \% y = x_2 \% y$，那么 $(x_1 - x_2) \% y = 0$。从这个性质我们还可以证明，$x \% y$，$(x+1) \% y$，……，以及 $(x+y-1) \% y$ 都是不同的数。

查看本页原始扫描图

囚犯帽子问题

一百名囚犯被告知明天有机会获得自由。他们都知道每个人会得到一顶红色或蓝色的帽子戴在头上。每个囚犯都能看到其他所有人的帽子颜色，但看不到自己的。帽子颜色是随机分配的，一旦帽子戴在每个囚犯头上，他们之间就不能以任何形式交流，否则立即处决。囚犯将按随机顺序被叫出，被叫到的囚犯要猜测自己帽子的颜色。每个囚犯大声说出自己猜测的颜色，让其他人都能听到。如果囚犯猜对了自己帽子的颜色，他将立即获释；否则将被处决。他们有一整晚的时间来共同制定一个策略，以拯救尽可能多的囚犯。他们能采用的最佳策略是什么？能保证拯救多少名囚犯？

14脚注 14提示：第一个囚犯可以看到其他 99 名囚犯的红帽子和蓝帽子数量。一种颜色的数量是奇数，另一种是偶数。 解答： 至少可以拯救 99 名囚犯。关键在于第一个囚犯，他能看到其他所有人的帽子。如果他看到的红帽子数量是奇数，他就宣布自己的帽子是红色；否则宣布是蓝色。他猜对自己帽子颜色的概率是 1/2。其他每个人都能结合“红帽子在其余 99 名囚犯（不包括第一个）中是否为奇数”这一信息，以及其他 98 名囚犯（不包括第一个和自己）的帽子颜色，推断出自己的帽子颜色。例如，如果红帽子在其他 99 名囚犯中是奇数个。

那么一个戴红帽子的囚犯会在其他 98 人（不包括第一个和自己）中看到偶数个红帽子，从而推断出自己戴的是红帽子。两种颜色的情况很简单，不是吗？如果有 3 种可能的帽子颜色：红、蓝、白呢？他们能采用的最佳策略是什么？能保证拯救多少名囚犯？15脚注 15提示：一个数是奇数仅仅意味着 $x \% 2 = 1$。这里有 3 种颜色，所以你可能需要考虑 $x \% 3$。 解答： 答案仍然是至少 99 名囚犯将获救。不同之处在于，现在第一个囚犯只有 1/3 的生存机会。让我们使用以下计分系统：红=0，绿=1，蓝=2。第一个囚犯计算

查看本页原始扫描图

其余 99 名囚犯并计算 s%3。如果余数为 0，则宣布为红色；如果余数为 1，则为绿色；如果余数为 2，则为蓝色。他有 1/3 的几率存活，但其余所有囚犯都可以从余数中确定自己的分数（颜色）。让我们考虑 99 名囚犯中的一名囚犯 i（不包括第一名囚犯）。他可以计算出其他 98 名囚犯的总分数（x）。由于 (x+0)%3、(x+1)%3 和 (x+2)%3 都不同，因此从第一名囚犯给出的余数（针对包括 i 在内的 99 名囚犯）中，他可以确定自己的分数（颜色）。例如，如果囚犯 i 看到其他 98 名囚犯（不包括第一名囚犯和他自己）中有 32 名红色、29 名绿色和 37 名蓝色。这 98 名囚犯的总分是 103。如果第一名囚犯宣布余数为 2（绿色），那么囚犯 i 就知道他自己的颜色是绿色（1），因为在 103、104 和 105 中，只有 104%3 = 2。理论上，类似的策略可以扩展到任何数量的颜色。

当然，这需要所有囚犯都具备非凡的记忆力和计算能力。

除以 9

给定一个任意整数，提出一个规则来判断它是否能被 9 整除，并证明它。解答：希望你还记得高中数学课上的规则。将整数的所有数字相加。如果和能被 9 整除，则该整数能被 9 整除；否则，该整数不能被 9 整除。但我们如何证明它呢？我们将原始整数表示为 \(a=a_n10^n +a_{n-1}10^{n-1} +---+a_110^1+a_0\)。我们基本上陈述，如果 \(a_n +a_{n-1} +---+a_1+a_0 =9x\)（x 是一个整数），那么 a 也能被 9 整除。证明很简单： 对于任何 \(a=a_n10^n +a_{n-1}10^{n-1} +---+a_110^1+a_0\)，令 \(b=a-(a_n+a_{n-1}+---+a_1+a_0)\)。我们有 \(b=a_n(10^n-1)+a_{n-1}(10^{n-1}-1)+---+a_1(10^1-1)\)。

因为所有 \((10^k-1)\)，\(k=1,\dots,n\) 都能被 9 整除，所以 b 能被 9 整除。由于 b 和 9x 都能被 9 整除，所以 \(a=b+9x\) 也必须能被 9 整除。（类似地，你也可以证明 \(a =(-1)^n a_n +(-1)^{n-1}a_{n-1} +---+(-1)^1a_1 +a_0 =11x\) 是 a 能被 11 整除的充要条件。）

查看本页原始扫描图

变色龙的颜色

一个遥远的岛屿上有三种类型的变色龙，数量如下：13 只红色变色龙，15 只绿色变色龙和 17 只蓝色变色龙。每当两只不同颜色的变色龙相遇时，它们都会变成第三种颜色。例如，如果一只绿色变色龙遇到一只红色变色龙，它们都会变成蓝色。是否有可能让所有变色龙都变成同一种颜色？为什么？16脚注 16提示：考虑数字对 3 取模。 解答：不可能让所有变色龙都变成同一种颜色。有几种方法可以证明这个结论。这里我们讨论其中两种。 方法 1。由于数字 13、15 和 17 是“大”数字，我们可以将问题简化为三种颜色数量为 0、2 和 4 的情况。（要理解这一点，你需要意识到，如果组合 (m+1,n+1,p+1) 可以转换为同一种颜色，那么组合 (m,n,p) 也可以转换为同一种颜色。）组合 (0,2,4) 能否转换为组合 (0,0,6)？答案是否定的，如图 2.3 所示：

实际上，组合 (1,2,3) 等价于组合 (0,1,2)，它只能转换为另一个 (0,1,2)，但永远不会达到 (0,0,3)。 方法 2。另一种更根本的方法是认识到，为了让所有变色龙变成同一种颜色，在某个中间阶段，两种颜色的数量必须相同。要理解这一点，只需想象最终阶段之前的那个阶段。它必须是组合 (1,1,x)。要使两种不同颜色的变色龙数量相同，它们对 3 取模的结果也必须相同。我们开始时是 15 = 3x，13 = 3y + 1，和 17 = 3z + 2 只变色龙。当两只不同颜色的变色龙相遇时，我们会有三种可能的情况：

查看本页原始扫描图

\[ \begin{cases} (3x + 2, 3y, 3z + 1) \\ (3x, 3y + 1, 3z + 2) \\ (3(x-1) + 2, 3y, 3(z+1) + 1) \end{cases} = \begin{cases} (3x', 3y'+1, 3z'+2), & \text{一只 y 遇到一只 z} \\ (3x', 3y'+1, 3z'+2), & \text{一只 x 遇到一只 z} \\ (3x', 3y'+1, 3z'+2), & \text{一只 x 遇到一只 y} \end{cases} \] 所以模式被保留下来，我们永远不会得到两种颜色具有相同的模 3 余数。换句话说，我们无法使两种颜色的数量相同。因此，变色龙不可能变成同一种颜色。本质上，两只变色龙相遇后，任何一对颜色的相对变化要么是 0，要么是 3。为了让所有变色龙变成一种颜色，至少有一对颜色的数量差必须是 3 的倍数。

补充说明： 方法 2 的核心是寻找一个在变化过程中保持不变的量（不变量）。这里，每种颜色的数量对 3 取模的余数模式（即余数组合）在每次相遇后都保持不变。初始的余数组合是 (0, 1, 2)（因为 15%3=0, 13%3=1, 17%3=2）。而最终所有变色龙同色时，余数组合只能是 (0,0,0) 或 (1,1,1) 或 (2,2,2)。由于我们无法从 (0,1,2) 通过规则操作得到这些组合，因此目标无法实现。

2.8 数学归纳法

归纳法是数学中，尤其是离散数学中最强大和最常用的证明技术之一。许多涉及整数的问题都可以用归纳法解决。归纳证明的一般步骤如下：

• 声明证明使用归纳法，并定义一个合适的谓词 \(P(n)\)。
• 证明基本情况 \(P(1)\)，或谓词为真的任何其他最小数字 \(n\)。
• 证明对于每个整数 \(n\)，\(P(n)\) 蕴含 \(P(n+1)\)。或者，在强归纳论证中，你证明 \(P(1), P(2), \dots\), 和 \(P(n)\) 共同蕴含 \(P(n+1)\)。

在大多数情况下，真正的困难不在于归纳步骤，而在于将问题表述为归纳问题并想出合适的谓词 \(P(n)\)。问题的简化版本通常可以帮助你识别 \(P(n)\)。

硬币分割问题

你将 1000 枚硬币分成两堆，并计算每堆的硬币数量。如果第一堆有 \(x\) 枚硬币，第二堆有 \(y\) 枚硬币，你将 \(x\) 乘以 \(y\) 得到 \(xy\)。然后你进一步分割这两堆，重复相同的计数和乘法过程，并将新的乘法结果加到原来的结果上。例如，你将 \(x\) 分割成 \(x_1\) 和 \(x_2\)，将 \(y\) 分割成 \(y_1\) 和 \(y_2\)，那么总和就是 \(xy + x_1x_2 + y_1y_2\)。重复这个过程，直到你只剩下每堆 1 枚硬币。最终的总和是多少？（最终的 1 不计入总和。）证明无论你如何分割，你总是得到相同的答案。

查看本页原始扫描图

解答：

设 $n$ 为硬币的数量，$f(n)$ 为最终的总和。由于 $n=1000$ 是一个很大的数字，一个解决方案不太可能立刻浮现在脑海中。如果你不确定如何着手解决问题，从最简单的情况开始寻找规律总是有益的。对于这个问题，基本情况是 $n=2$。显然，唯一的分割是 $1+1$，最终的总和是 $1$。当 $n=3$ 时，第一次分割是 $2+1$，我们有 $xy=2$，而 $2$ 枚硬币的堆会进一步产生额外的乘积结果 $1$，所以最终的总和是 $3$。这个分析也给出了一个提示：当 $n$ 枚硬币被分成 $x$ 枚和 $n-x$ 枚时，总和将是 $f(n)=x(n-x)+f(x)+f(n-x)$。$4$ 枚硬币可以分成 $2+2$ 或 $3+1$。在这两种情况下，我们都可以应用 $x(n-x)+f(x)+f(n-x)$，并得到相同的最终总和 $6$。

断言：

对于 $n$ 枚硬币，无论中间如何分割，最终的总和是 $\frac{n(n-1)}{2}$。我们该如何证明它呢？答案对你来说应该是清晰的：通过强数学归纳法。我们已经证明了基本情况 $n=2,3,4$ 的命题。假设命题对于 $n=2, \dots, N-1$ 枚硬币成立，我们需要证明它对于 $n=N$ 枚硬币也成立。再次应用方程 $f(n) = x(n-x)+f(x)+f(n-x)$。

如果将 $N$ 枚硬币分成 $x$ 枚和 $N-x$ 枚，我们有 \[ f(N) = x(N-x) + f(x) + f(N-x) \] \[ = x(N-x) + \frac{x(x-1)}{2} + \frac{(N-x)(N-x-1)}{2} \] \[ = \frac{2x(N-x) + x^2 - x + (N-x)(N-x-1)}{2} \] \[ = \frac{2xN - 2x^2 + x^2 - x + (N^2 - Nx - N - Nx + x^2 + x)}{2} \] \[ = \frac{2xN - x^2 - x + N^2 - 2Nx - N + x^2 + x}{2} \] \[ = \frac{N^2 - N}{2} = \frac{N(N-1)}{2} \] 所以它确实对于 $n=N$ 也成立，并且 $f(n)=\frac{n(n-1)}{2}$ 对于任何 $n \ge 2$ 都成立。

将结论应用于 $n=1000$，我们得到 $f(n)=1000 \times 999 / 2$。

补充说明： 这个问题的直观理解是，每次切割（分割）一枚硬币堆，都会产生一个乘积项，这个乘积项等于被分割堆中硬币数量的某种组合。最终总和 $\frac{n(n-1)}{2}$ 恰好是从 $n$ 枚硬币中无序选取 2 枚的组合数。可以这样理解：每对硬币在它们第一次被分到不同堆中的那次分割时，恰好贡献了 1 到总和中。因此，总和与分割方式无关，只与初始硬币总数有关。

巧克力棒问题

一块巧克力有 $6$ 行和 $8$ 列（共 $48$ 个 $1 \times 1$ 的小方格）。你通过一系列的切割将它分成单个的小方格。每次，将一块长方形切成两块更小的长方形。例如，在第一步，你可以将 $6 \times 8$ 的巧克力块切成一块 $6 \times 3$ 和一块 $6 \times 5$。将巧克力块分成 $48$ 个小方格总共需要多少次切割？ 17脚注 17$f(2)=1$, $f(3)-f(2)=2$ and $f(4)-f(3)=3$ 应该能给你足够的提示，让你意识到规律是 \[ f(n) = 1+2+\dots+(n-1) = \frac{n(n-1)}{2}. \]

查看本页原始扫描图

巧克力棒问题

解答： 设巧克力棒有 $m$ 行和 $n$ 列。由于 $m=6$ 和 $n=8$ 的情况没有特殊之处，我们应该找到一个对所有 $m$ 和 $n$ 都适用的通用解。让我们从 $m=1$ 和 $n=1$ 的基本情况开始。所需的断裂次数显然是 0。对于 $m>1$ 和 $n=1$，断裂次数是 $m-1$；同理，对于 $m=1$ 和 $n>1$，断裂次数是 $n-1$。因此，对于任何 $m$ 和 $n$，如果我们先将巧克力分成 $m$ 行，这需要 $m-1$ 次断裂，然后将每一行分成 $n$ 小块，这需要 $m(n-1)$ 次断裂，总断裂次数是 $(m-1) + m(n-1) = mn-1$。如果我们先将其分成 $n$ 列，然后将每一列分成 $m$ 小块，总断裂次数也是 $mn-1$。但是，对于其他断裂顺序，总断裂次数是否总是 $mn-1$ 呢？当然是。我们可以用强归纳法来证明这一点。

我们已经证明了对于基本情况 $m \ge 1, n=1$ 和 $m=1, n \ge 1$，断裂次数是 $mn-1$。为了证明对于一般的 $m \times n$ 情况，让我们假设该命题对于行数 $<m$，列数 $\le n$ 以及行数 $\le m$，列数 $<n$ 的情况是成立的。如果第一次断裂沿着一行进行，并且将其分成两个较小的块 $m \times n_1$ 和 $m \times (n-n_1)$，那么总断裂次数是 $1 + (m \times n_1 - 1) + (m \times (n-n_1) - 1) = mn-1$。这里我们使用了行数 $\le m$，列数 $<n$ 的结果。同理，如果将其分成两个块 $m_1 \times n$ 和 $(m-m_1) \times n$，则总断裂次数是 $1 + (m_1 \times n - 1) + ((m-m_1) \times n - 1) = mn-1$。

因此，为了将巧克力棒分成 $m \times n$ 小块，总断裂次数总是 $mn-1$。对于 $m=6$ 和 $n=8$ 的情况，断裂次数是 47。尽管归纳法是解决这个问题的标准方法，但如果你注意到一个重要事实，其实有一个更简单的解决方案：每次断裂都会使块的数量增加 1，因为它总是将一个块分成两个。开始时，我们有一个块。结束时，我们将有 $mn$ 个块。因此，断裂次数必须是 $mn-1$。

赛道

假设你身处一个单向的环形赛道。赛道上有 $N$ 个加油站随机分布在不同的位置，这些加油站的总油量足以让你的汽车跑完一圈。假设你的汽车油箱最初是空的，但你可以选择赛道上的任何位置作为起点，并沿途收集加油站的汽油来加满你的油箱。你是否总能选择一个起点，使你的汽车能够完成整个赛程？！ 18脚注 18提示： 从 $N=1, 2$ 开始，并使用归纳法解决问题。

查看本页原始扫描图

解答： 如果你对如何解决问题感到困惑，再次从最简单的情况（$N = 1, 2$）开始，并考虑使用归纳法。不失一般性，我们假设赛道的周长为 1。对于 $N = 1$，这个问题很简单。只需从有油罐的位置出发即可。对于 $N = 2$，问题仍然很简单。让我们用一张图来可视化这个方法。如图 2.4A 所示，油罐 1 和油罐 2 中的油量（以汽车可以行驶的距离表示）分别为 $x_1$ 和 $x_2$，所以 $x_1 + x_2 = 1$。对应的路段长度为 $y_1$ 和 $y_2$，所以 $y_1 + y_2 = 1$。由于 $x_1 + x_2 = 1$ 且 $y_1 + y_2 = 1$，我们必须有 $x_1 \ge y_1$ 或 $x_2 \ge y_2$（$x_1 < y_1$ 和 $x_2 < y_2$ 不可能同时成立）。

如果 $x_1 \ge y_1$，我们可以从油罐 1 出发，它有足够的油到达油罐 2，然后从油罐 2 获得更多汽油来完成整圈。否则，我们就从油罐 2 出发，沿途拾取油罐 1 的汽油来完成整圈。

$N = 2$ 的论证也为我们提供了归纳步骤的提示。现在我们要证明，如果该命题对 $N = n$ 成立，那么对 $N = n+1$ 也成立。如图 2.4B 所示，对于 $N = n+1$，我们有 $x_1 + x_2 + \dots + x_{n+1} = 1$ 和 $y_1 + y_2 + \dots + y_{n+1} = 1$。因此，必须至少存在一个 $i$（$1 \le i \le n+1$），使得 $x_i \ge y_i$。这意味着每当汽车到达 $x_i$ 时，它可以带着更多的油到达 $x_{i+1}$（对于 $i = n+1$，则到达 $i=1$）。换句话说，我们实际上可以将 $x_i$ 和 $x_{i+1}$ “合并” 到 $x_i$ 位置的一个油罐中，其油量为 $x_i + x_{i+1}$（并消除油罐 $i+1$）。

但这样的合并将 $N = n+1$ 的问题简化为 $N = n$ 的问题，而该命题对 $N = n$ 是成立的。所以该命题对 $N = n+1$ 也成立。因此，对于任何 $N$，我们总能在赛道上选择一个起点来完成整圈。

补充说明： 这个归纳法的核心思想是：总能找到一个油罐 $i$，其油量 $x_i$ 足以支撑汽车开到下一个油罐 $i+1$。这样，我们就可以将这两个油罐“虚拟合并”，把问题规模从 $n+1$ 减少到 $n$，从而利用归纳假设。

这个问题还有另一种方法，它提供了起点的具体选择方案。想象你有一辆汽油充足的汽车可以跑完一圈。你将那辆车放在一个随机选择的油罐位置，并驾驶它跑完一整圈。每当你到达一个油罐时（包括初始位置），记录下你在从该油罐加油之前油箱中的油量。跑完一圈后，查看你的记录，找到最低的油量读数。如果汽车初始油箱为空，那么与最低读数对应的油罐位置就应该是你的起点。（要完全理解这个论证可能需要一些思考。如果你觉得这个推理不明显，我建议你再次画图并仔细思考这个论证。）

查看本页原始扫描图

2.9 反证法

在反证法（或称间接证明）中，你通过证明如果一个命题为假，就会导致某种逻辑矛盾或荒谬的结果，从而证明该命题必须为真。

无理数

你能证明 $\sqrt{2}$ 是一个无理数吗？有理数是可以表示为两个整数之比的数；否则就是无理数。 解答： 这是一个经典的反证法例子。如果 $\sqrt{2}$ 不是无理数，它可以表示为两个整数 $m$ 和 $n$ 的比值。如果 $m$ 和 $n$ 有任何公因数，我们可以通过同时除以公因数来消除它。所以最终，我们会得到一对没有公因数的 $m$ 和 $n$。（这称为最简分数。）由于 $m/n = \sqrt{2}$，我们有 $m^2 = 2n^2$。所以 $m^2$ 必须是偶数，因此 $m$ 也必须是偶数。因为 $m$ 是偶数，我们将其表示为 $2x$，其中 $x$ 是整数。那么 $m^2 = 4x^2$，并且我们也有 $n^2 = 2x^2$，这意味着 $n$ 也必须是偶数。但是 $m$ 和 $n$ 都是偶数，这与之前 $m$ 和 $n$ 没有公因数的陈述相矛盾。所以 $\sqrt{2}$ 必须是一个无理数。

彩虹帽

七名囚犯有机会在明天获得释放。一名行刑官会给每个囚犯戴上一顶帽子。每顶帽子可以是彩虹七色中的任意一种，帽子的颜色完全由行刑官决定。每个囚犯可以看到其他六名囚犯的帽子颜色，但看不到自己的。他们不能以任何形式与他人交流，否则将立即被处决。然后每个囚犯写下对自己帽子颜色的猜测。如果至少有一名囚犯正确猜中了自己帽子的颜色，他们将全部立即获释；否则他们将被处决。他们有一个晚上的时间来制定策略。是否存在一种策略，可以保证他们一定能获释？解答： 这个问题通常被认为比模运算章节中的囚徒问题更难。在之前的囚徒问题中，囚徒们能听到其他人的猜测。因此，一个囚徒的宣告就提供了其他囚徒所需的全部信息。而在这个问题中，囚徒们不会知道其他人的猜测是什么。要解决这个问题，确实需要一个“灵光一现”的时刻。这个“灵光一现”的关键由提示给出。

一旦你意识到，如果我们把颜色编码为 0-6，那么 \( (\sum_{i=1}^{7} x_i) \% 7 \) 的结果也必然是 0, 1, 2, 3, 4, 5 或 6 中的一个。那么，每个囚徒 \(i\)（我们也把他们标记为 0-6）应该给出一个猜测 \(g_i\)，使得 \(g_i\) 与其他 6 位囚徒的帽子颜色代码之和除以 7 的余数等于 \(i\)，其中 \(g_i\) 是 0 到 6 之间的一个唯一数字。例如，囚徒 0 的猜测应满足 \( (g_0 + \sum_{k \neq 0} x_k) \% 7 = 0 \)。这样，我们就可以保证对于 \(i = 0, 1, 2, 3, 4, 5, 6\)，至少有一个 \(g_i = x_i\)。我们可以用反证法轻松证明这个结论。

如果对于所有 \(i\) 都有 \(g_i \neq x_i\)，那么对于每个 \(i\)，都有 \( (\sum_{k \neq i} x_k) \% 7 \neq i \)（因为 \( g_i + \sum_{k \neq i} x_k \neq i \)，且 \(g_i\) 和 \(x_i\) 都在 0 到 6 之间）。但如果对于所有 \(i = 0, 1, 2, 3, 4, 5, 6\) 都有 \(g_i \neq x_i\)，那就意味着 \( (\sum_{i=1}^{7} x_i) \% 7 \) 不等于 0, 1, 2, 3, 4, 5, 6 中的任何一个，这显然是不可能的。因此，至少有一个 \(g_i\) 必须等于 \(x_i\)。结果就是，使用这个策略，他们保证能被释放。

补充说明： 这个策略的核心是“错位覆盖”。7个囚徒的猜测 \(g_i\) 被设计成分担了所有可能的余数结果（0到6）。由于7顶帽子颜色总和除以7的余数 \(S\) 必然在0到6之间，那么“负责”余数 \(S\) 的那个囚徒（即编号为 \(S\) 的囚徒），他的猜测 \(g_S\) 就必须等于他自己帽子的颜色 \(x_S\)，才能使得等式 \( (g_S + \sum_{k \neq S} x_k) \% 7 = S \) 成立。因为 \( (g_S + \sum_{k \neq S} x_k) \% 7 = (g_S + (总码和 - x_S)) \% 7 = (g_S - x_S + S) \% 7 \)，要让它等于 \(S\)，就必须有 \(g_S = x_S\)。其他猜错的囚徒不会影响这个必然性。

19脚注 19提示：让我们用代码 0-6 来表示彩虹的 7 种颜色，并用 \(x_i\) 表示囚徒 \(i\) 的帽子颜色代码。那么 \( (\sum_{i=1}^{7} x_i) \% 7 \) 的结果必然是 0, 1, 2, 3, 4, 5 或 6。7 个囚徒一共能做出多少次猜测？