经典面试智力题

本章目标：掌握大厂面试中最常考的经典智力题，每道题给出完整最优解。

题型特点

这些是"必须知道答案"的题——它们在 Google、Meta、Amazon、字节跳动等公司的面试中出现频率极高。面试官不期待你现场推导出答案（虽然能做到更好），但期望你见过类似题型、能讲出解题思路。

这些题的共同特点：问题简洁、答案优雅、推理过程考验结构化思维。

高频考点清单

题型	代表题
赛马/分组	25 匹马 5 赛道
时间测量	烧绳子、沙漏
过桥问题	4 人 17 分钟
称重问题	8 球、12 球、9 球
信息论下界	球称重、找不同
缩放规律	你缩小到硬币大小
倒水问题	3-5 加仑桶
概率面试	蒙提霍尔、生日悖论
时钟问题	时针分针何时重合
容斥问题	数字根、奇偶性

---

题目 1：25 匹马 5 赛道找前 3 名

题面

你有 25 匹马和一个 5 条赛道的赛道。你没有秒表，只能通过比赛知道相对名次（每场比赛记录 5 匹马的排名）。问：最少需要多少场比赛才能确定 25 匹马中最快的 3 匹？

拆解与思考

第一步（5 场）：把 25 匹马分成 5 组，每组 5 匹，各赛一场。记录每组内部排名。

A 组：A1 > A2 > A3 > A4 > A5
B 组：B1 > B2 > B3 > B4 > B5
C 组：C1 > C2 > C3 > C4 > C5
D 组：D1 > D2 > D3 > D4 > D5
E 组：E1 > E2 > E3 > E4 > E5

第二步（第 6 场）：让 5 个小组第一名（A1, B1, C1, D1, E1）赛一场。假设结果是 A1 > B1 > C1 > D1 > E1。

关键推理（淘汰分析）：

• A1 是所有 25 匹马中最快的（6 场不败）。
• D 组和 E 组的第一名只排第 4、5，整组都不可能出前 3，淘汰。
• C 组只有 C1 可能是第 3 名（C2、C3 不如 C1，C1 不如 B1 和 A1，最多第 3）。
• B 组的 B1 可能第 2、B2 可能第 3。B3 及以下淘汰。
• A 组的 A1 第 1，A2 可能第 2 或第 3，A3 可能第 3。

第三步（第 7 场）：候选前 3 名（除 A1 外）= A2, A3, B1, B2, C1，共 5 匹。让它们赛一场，取前 2 名，加上 A1 就是总前 3。

答案

最少需要 7 场比赛。

严谨下界证明

为什么不能更少？

• 前 3 名至少要"参加过比赛"才能知道名次（秒表不存在，全靠比较）。
• 25 匹马至少要 25/5 = 5 场才能都参加过比赛。
• 5 场之后，每组的第 1 名之间必须比一次（否则不知谁是最快），共 6 场。
• 第 6 场后，仍然有 5 匹马（A2, A3, B1, B2, C1）可能是总前 3，至少还要 1 场。
• 总共 ≥ 7 场。✓

延伸：找前 5 名

复杂得多，至少需要 8-10 场（精确下界是 9 场）。需要更精细的分组分析。

---

题目 2：烧绳子测 15 分钟

题面

你有两根特殊的绳子。每根绳子从一头点燃烧完恰好需要 60 分钟。但绳子不均匀——可能前一半 50 分钟、后一半 10 分钟。你只有这两根绳子和一个打火机。如何精确测出 15 分钟？

拆解与思考

关键性质：虽然绳子燃烧不均匀，但一根绳子从一头烧到另一头固定是 60 分钟。如果从两头同时点，烧完时间恰好减半 = 30 分钟（不管中间哪里先烧完，火会从两端推进直到相遇）。

方案：

1. 第 0 分钟：点燃绳子 1 的两头，同时点燃绳子 2 的一头。
2. 第 30 分钟：绳子 1 烧完（两头烧完 = 30 分钟）。此时立刻点燃绳子 2 的另一头。
3. 绳子 2 此时还剩 30 分钟的量。从两头烧只需 15 分钟。
4. 第 45 分钟：绳子 2 烧完。

从第 30 分钟到第 45 分钟，恰好 15 分钟。

答案

点燃绳 1 两头 + 绳 2 一头；绳 1 烧完时（30 分钟），点燃绳 2 另一头；绳 2 烧完时再过 15 分钟。

延伸：可以测出哪些时间？

时间	方案
30 分	绳 1 两头同时点
60 分	绳 1 一头点
45 分	30 + 15（经典方案）
75 分	60 + 15（绳 1 烧完点绳 2 两头）
90 分	60 + 30

利用 N 根绳子可测的时间是 60 × k/2^m（k 整数，m 受绳数限制）。

---

题目 3：过桥问题（4 人 17 分钟）

题面

4 个人晚上过一座桥，只有一只手电筒。桥一次最多走 2 人，必须带手电筒（可以往返携带）。4 人过桥速度不同：1 分钟、2 分钟、5 分钟、10 分钟。两人一起走时按慢的人计。问：最少需要多少分钟让所有人都过桥？

拆解与思考

核心原则：让慢的人少走。尤其 10 分钟和 5 分钟的人不能各自单独过桥后再回来。

策略一（让最快的人来回送手电筒）：

1分 + 2分 过去 → 2 分钟
1分 回来       → 1 分钟
1分 + 5分 过去 → 5 分钟
1分 回来       → 1 分钟
1分 + 10分 过去 → 10 分钟
总计：2+1+5+1+10 = 19 分钟

还可以优化。

策略二（让两个慢的人一起过桥）：

1分 + 2分 过去   → 2 分钟  （对岸：2分）
1分 回来         → 1 分钟  （对岸：2分）
5分 + 10分 过去  → 10 分钟 （对岸：2分、5分、10分）
2分 回来         → 2 分钟
1分 + 2分 过去   → 2 分钟
总计：2+1+10+2+2 = 17 分钟 ✓

关键洞察：让两个最慢的人（5分和10分）一起过桥，只消耗一次 10 分钟，而不是各过一次。

答案

最少需要 17 分钟。

一般策略

设四人速度 a ≤ b ≤ c ≤ d。两种方案：

• 方案 A（最快人送手电筒）：(a + b) + a + (a + c) + a + (a + d) = 4a + b + c + d。
• 方案 B（两个慢的一起）：(a + b) + a + (c + d) + b + (a + b) = 2a + 3b + c + d（这里 a + b 是首尾，重新推导：(a+b) + a + (c+d) + b + (a+b) 不对，应该是 (a+b) + a + (c+d) + b + (a+b) 即 3b + 2a + c + d）。

正确公式：取 min(方案 A, 方案 B)。

通用贪心策略：每次都让两个最慢的人一起过桥（用两个最快的接送手电筒）。

推广：N 人过桥

N 人过桥问题没有简单闭式解，但贪心策略通常有效：每次让两个最慢的过桥，用两个最快的来回送手电。

代码：

def bridge_time(times):
    """times: 每人过桥时间，升序"""
    times.sort()
    total = 0
    while len(times) > 3:
        a, b = times[0], times[1]
        c, d = times[-2], times[-1]
        # 两种方案选优
        total += min(2*b + a + d,  # a 和 d 过，a 回，b 和 c 过，b 回
                     2*a + c + d)  # a 和 d 过，a 回，a 和 c 过，a 回（错，应是 a+d 过 + a 回 + a+c 过 + a 回 = 2a + c + d）
        times = times[:-2]
    if len(times) == 3:
        total += sum(times)
    elif len(times) == 2:
        total += max(times)
    else:
        total += times[0]
    return total

---

题目 4：8 个球找偏重的

题面

8 个外观相同的球，其中 7 个重量相同，1 个偏重。你有一架天平。最少称几次能找出偏重的那个？

拆解与思考

天平每次有 3 种结果：左重、右重、平衡。所以每次称量将信息量三分。

8 个球，需要区分 8 种可能。3ⁿ ≥ 8 → n ≥ 2（因为 3² = 9 ≥ 8）。理论最少 2 次。

方案：

第一次：把 8 个球分成 3+3+2 三组。天平两边各放 3 个。

• 如果平衡：偏重球在未称的 2 个中。第二次：称这 2 个，重的那个就是。
• 如果左边重：偏重球在左边 3 个中。第二次：取左边 3 个中任意 2 个称。
  • 平衡 → 第 3 个（没称的）是偏重的。
  • 不平衡 → 重的那边那个是偏重的。
• 如果右边重：对称处理。

答案

最少 2 次称量。

延伸

信息论下界：

球数	已知偏重/偏轻	称量次数
3	已知	1
9	已知	2
27	已知	3
3ⁿ	已知	n
12	不知	3
13	不知	3（需额外标准球）

12 球问题（不知重轻）：经典的"称 3 次找出 12 球中异常的那个"，难度高得多。每次称量需精心设计，让 3 种结果对应的可能性数尽量相等（信息熵最大化）。

---

题目 5：25 匹马限时变体

题面

一条赛道，25 匹马，每次只能跑 5 匹。没有秒表。你需要在 1 分 30 秒内找出最快的 3 匹马。每场比赛需要 30 秒。问你能做到吗？

拆解与思考

1 分 30 秒 = 90 秒。每场 30 秒，意味着最多跑 3 场。

但我们已经知道 25 匹马找前 3 名至少需要 7 场。所以 3 场不可能覆盖所有 25 匹马。

关键：这是面试中的"陷阱题"。正确回答是：做不到。

但面试官真正想看的，是你能否清晰解释为什么做不到：

• 每匹马至少要跑过 1 次才能评估，25 匹马 / 5 赛道 = 最少 5 场（光分组就要 5 场）。
• 5 场 × 30 秒 = 150 秒 > 90 秒。

答案

做不到。 仅分组就需要 5 场（150 秒），超过时间限制 90 秒。

如果面试官追问"最少多少时间"，答案是 7 场 × 30 秒 = 210 秒（3 分 30 秒）。

延伸

这类题考的不是计算能力，而是你识别"不可能任务"的判断力。很多人不假思索开始算"怎么 3 场搞定"，浪费了面试时间。

类似陷阱题：

• 给你 1L 和 3L 量杯，能量出 2L 水吗？（可以，3-1=2）
• 给你 1L 和 3L 量杯，能量出 π L 水吗？（不可能）
• 用一根直尺量出一座山的体积？（不可能，需要其他工具）

---

题目 6：谷歌经典——你被缩小了

题面

你被缩小到只有一枚硬币那么高，质量也按比例缩小。你被扔进一台正在运转的搅拌机（玻璃壁，刀片在底部）里。搅拌机 60 秒后启动。你怎么逃生？

拆解与思考

错误思路：爬玻璃壁（太滑）、躲刀片下面（空间不够）、打破玻璃（缩小的你没有力气）。

正确思路——物理分析：

关键洞察在于缩放规律。你缩小到原来的 1/N：

• 你的体积和质量缩小到 1/N³。
• 你的肌肉截面积缩小到 1/N²。
• 所以你的力量/体重比 = (1/N²) / (1/N³) = N 倍！

也就是说，缩小后你的相对力量变成了原来的 N 倍。如果你缩到原来 1/100，你的相对力量是 100 倍。

蚂蚁能举起自身 50 倍的重量就是这个原理。

逃生方案：你的相对弹跳高度是原来的 N 倍（因为你的加速度不变但体重变轻很多）。只需直接跳——缩小的你可以轻松跳出搅拌机口。

答案

直接跳出去。因为缩放规律使你的力量/体重比大幅提升，弹跳高度足够跳出搅拌机。

缩放规律的更多应用

现象	解释
蚂蚁举 50 倍体重	F ∝ L², M ∝ L³, F/M ∝ 1/L
大象不能跳	太大，落地冲击会断腿
巨人不存在	骨骼强度 ∝ L², 体重 ∝ L³，太大压垮自己
小动物心率快	散热 ∝ L², 产热 ∝ L³，需快心率维持体温
大型船只更经济	阻力 ∝ L², 载货 ∝ L³，规模经济

延伸

为什么巨型蜘蛛不可能存在？蜘蛛的腿力 ∝ 截面² ∝ L²，体重 ∝ L³。如果蜘蛛放大 100 倍，腿力增加 10⁴ 倍，但体重增加 10⁶ 倍——腿会断。

工程意义：摩天大楼、桥梁、飞机的设计都受缩放规律约束。

---

题目 7：3 升和 5 升量杯量 4 升水

题面

给你一个 3 升杯、一个 5 升杯（都无刻度）、无限水。如何量出恰好 4 升水？

拆解与思考

方法一（先装满 5）：

1. 装满 5 → (0, 5)。
2. 把 5 倒入 3 → (3, 2)。
3. 倒空 3 → (0, 2)。
4. 把 5 中的 2 倒入 3 → (2, 0)。
5. 装满 5 → (2, 5)。
6. 把 5 倒入 3（3 桶只能再装 1）→ (3, 4)。

此时 5 升杯中正好 4 升。

方法二（先装满 3）：

1. 装满 3 → (3, 0)。
2. 倒入 5 → (0, 3)。
3. 再装满 3 → (3, 3)。
4. 倒入 5（5 桶只能再装 2）→ (1, 5)。
5. 倒空 5 → (1, 0)。
6. 把 3 中的 1 倒入 5 → (0, 1)。
7. 装满 3 → (3, 1)。
8. 倒入 5 → (0, 4)。

此时 5 升杯中正好 4 升。

答案

两种方法都可以量出 4 升水，方法一 6 步，方法二 8 步。

数学背景

贝祖定理：若 gcd(a, b) | c，则存在整数 x, y 使 ax + by = c。

gcd(3, 5) = 1，1 整除 4，所以可解。一般 a, b 互素时可量出 1, 2, ..., a+b 中任意升数。

类似问题

• 7 升和 11 升杯量 13 升水？gcd(7, 11) = 1，可以。
• 4 升和 6 升杯量 5 升水？gcd(4, 6) = 2，2 不整除 5，不可能。

---

题目 8：硬币覆盖圆桌

题面

两人玩硬币游戏。轮流在圆桌上平放硬币（硬币不可重叠、不可悬空、不可移动）。谁放不下硬币谁输。两人都完美操作，先手必胜还是后手必胜？

拆解与思考

关键洞察——对称性：圆桌有完美的中心对称。

先手策略：第一步放正中央（圆心位置）。之后每次都把硬币放在对手刚才放的位置关于圆心对称的位置。

• 对手能放，我就能放（对称位置必然合法）。
• 对手放不下，我就赢了。

由于硬币不可重叠且桌面有限，游戏必然结束。先手必胜。

答案

先手必胜。第一步放圆心，之后每步对称模仿对手。

延伸：策略stealing论证

更一般的问题：任何有限的对称游戏（如井字棋、五子棋），先手至少不输——因为：

假设后手有必胜策略 S。先手随便走一步（"占位"），然后假装自己是后手用 S。如果 S 让先手回到最初占的位置，那这一步本身是合法的（因为已有更多棋子，原位置若合法现在也合法），相当于多走一步不亏。所以先手能"偷"用 S，矛盾。故先手有必胜或不败策略。

这叫 strategy stealing argument，证明井字棋先手必不败、五子棋先手必胜（无禁手）。

类似对称游戏

• 圆桌放硬币（先手必胜）
• 取石子游戏 Nim（按 XOR 和判断）
• 8×8 棋盘放多米诺骨牌（先手必胜，对角对称）

---

题目 9：100 个灯泡开关

题面

100 个灯泡初始关闭，编号 1-100。第 1 轮：把所有灯泡开关按一次（全亮）。第 2 轮：把 2 的倍数灯泡按一次。第 3 轮：把 3 的倍数灯泡按一次。... 第 100 轮：把 100 的倍数按一次。问最后亮着的灯泡有哪些？

拆解与思考

关键观察：灯泡 i 被按几次？答案是 i 的因子个数（每个因子 d 对应一轮"按 d 的倍数"时按到 i）。

• 因子个数为偶数：开关被按偶数次，回到初始状态（关）。
• 因子个数为奇数：开关被按奇数次，最终状态为亮。

哪些数的因子个数为奇数？

通常因子成对出现：d 和 n/d。但如果 d = n/d，即 d² = n，n 是完全平方数，此时 d 算一个（不算两个）。

所以只有完全平方数的因子个数为奇数。

答案

亮着的灯泡编号是 1, 4, 9, 16, 25, 36, 49, 64, 81, 100（100 以内的完全平方数）。

推广

• 1000 个灯泡：亮着的是 1, 4, 9, ..., 961（31²），共 31 个。
• n 个灯泡：亮着的有 ⌊√n⌋ 个。

工程意义

约数计数：因子个数函数 d(n)，数论中的基本函数。

def divisor_count(n):
    """n 的因子个数"""
    count = 0
    i = 1
    while i * i <= n:
        if n % i == 0:
            count += 1 if i * i == n else 2
        i += 1
    return count

---

题目 10：3 个灯泡与 3 个开关

题面

房间外 3 个开关，房间内 3 个灯泡（互相对应但不知哪个对哪个）。允许进入房间一次。如何确定对应关系？

拆解与思考

朴素思路：开 1 号开关进去看 → 只能确定 1 对应哪个，剩下两对无法区分。

关键洞察：灯泡除了亮/不亮，还有第三个状态：温度（热的、温的、冷的）。

策略：

1. 打开开关 A，等 5 分钟（让灯泡热起来）。
2. 关闭开关 A，立即打开开关 B。
3. 进入房间：
   • 亮的灯泡 → 对应 B。
   • 不亮但热的 → 对应 A。
   • 不亮且冷的 → 对应 C。

答案

利用灯泡温度作为第三个状态变量，3 个开关可在一次进入后全部识别。

延伸

变体：100 个开关、100 个灯泡，进入一次。能否全部识别？

利用等待时间差：开 1 号 100 分钟，关掉；开 2 号 99 分钟；…… 进入后用温度计精确测温，可全部识别。这是用连续变量承载信息的思路。

工程意义：通信中的多址接入（FDMA、TDMA、CDMA）——用频率、时间、码字区分多个信号，本质都是"用一个变量承载多个信息"。

---

题目 11：100 楼 2 鸡蛋问题

题面

100 层楼，2 个完全相同的鸡蛋。存在临界楼层 F：鸡蛋从 >F 层丢下会碎，≤F 层不碎。最少几次试验能确定 F？

拆解与思考

朴素二分：50 → 25 → 13... 但鸡蛋碎了只剩 1 个，必须从 1 楼逐层试。最坏 50 次。

正确思路——均匀分布策略：

设最多丢 x 次。第一个鸡蛋从第 x 层丢：

• 碎了：第二个鸡蛋从 1 试到 x-1，最多 x-1 次，加上第 1 次 = x 次。
• 没碎：第一个鸡蛋从 x + (x-1) 层丢（弥补已用 1 次）。
• 碎了：第二个鸡蛋在区间内逐层试，最多 x-2 次 + 2 = x+0 次。
• ...

递推：x + (x-1) + (x-2) + ... + 1 ≥ 100

x(x+1)/2 ≥ 100，x=14 时 14×15/2 = 105 ≥ 100 ✓。

答案

最少 14 次（100 层楼，2 鸡蛋）。

测试楼层：14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100。

推广：k 鸡蛋 n 层

动态规划：dp[k][m] = 最多用 k 个鸡蛋、m 次试验能测的最大楼层数。

递推：dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1

鸡蛋数	楼层数	最少试验
2	100	14
2	50	10
3	100	9
10	100	7

工程意义：最坏情况优化。在网络协议、缓存策略中常需考虑最坏延迟。

---

题目 12：海盗分金

题面

5 个海盗（A, B, C, D, E）抢到 100 枚金币。按等级 A > B > C > D > E。从 A 开始提议分配方案，所有人投票（包括提议者）。若 ≥ 半数同意则通过，否则提议者被扔下海，下一人继续。海盗都理性、自私、嗜血（同等收益时倾向扔人下海）。A 如何分配？

拆解与思考

逆向归纳：

只剩 E：E 全拿 100。但实际不会到这一步（D 会先分）。

剩 D 和 E：D 提议 D=100, E=0。投票：D 同意（1/2 ≥ 50%），通过。

剩 C, D, E：C 知道自己死后 D 全拿，所以 C 给 E 1 金币（E 比被 D 分得 0 好，必同意）。C 提议：C=99, D=0, E=1。投票：C 同意 + E 同意 = 2/3，通过。

剩 B, C, D, E：B 知道自己死后 C 分配是 (99, 0, 1)。B 给 D 1 金币（D 比 0 好，必同意）。B 提议：B=99, C=0, D=1, E=0。投票：B + D = 2/4 = 50%，通过。

剩 A, B, C, D, E（全部）：A 知道自己死后 B 分配是 (99, 0, 1, 0)。A 给 C 和 E 各 1 金币（他们都比被 B 分得 0 好，必同意）。A 提议：A=98, B=0, C=1, D=0, E=1。投票：A + C + E = 3/5 = 60%，通过。

答案

A 提议 (98, 0, 1, 0, 1)——A 拿 98 枚，C 和 E 各 1 枚。

推广：N 海盗

奇偶规律：N 个海盗时，提议者总能联合最少数量的"被排挤者"获得半数支持。

N	提议者收益	拿到 1 金币的人
2	100	无
3	99	最低 1
4	99	倒数第二
5	98	倒数第一和第三
6	98	倒数第二和第四
...

N ≥ 200 后规律更复杂——金币不够买支持，开始有人被扔下海。

工程意义

博弈论中的逆向归纳。这种"从终点倒推"的思路在 chess endgame、定价策略、谈判中都有应用。

---

题目 13：时针分针何时重合

题面

12 小时内，时针和分针重合多少次？分别是什么时刻？

拆解与思考

时针速度：360°/12h = 30°/h = 0.5°/min。 分针速度：360°/h = 6°/min。

相对速度：6 - 0.5 = 5.5°/min（分针每分钟比时针多走 5.5°）。

分针"追上"时针需要 360/5.5 ≈ 65.45 分钟。

12 小时 = 720 分钟。720 / (360/5.5) = 720 × 5.5 / 360 = 11 次。

答案

12 小时内重合 11 次。

具体时刻（从 12:00 开始）：约 1:05, 2:10, 3:16, 4:21, 5:27, 6:32, 7:38, 8:43, 9:49, 10:54, 12:00。

通用公式：第 k 次重合时间 = 12k/11 点（k=0,1,...,10）。

延伸

• 24 小时重合 22 次。
• 三针（时、分、秒）全重合只有 12:00（24 小时内 2 次）。
• 时针和分针成直线（不重合但反向）：12 小时 11 次。
• 时针和分针成直角：12 小时 22 次（每个周期 2 次）。

工程意义

周期性事件的对齐。在通信同步、信号采样、调度算法中都有应用——不同周期的事件对齐频率是它们周期的最小公倍数。

---

题目 14：井为什么是圆的（变体）

题面

为什么大部分井盖是圆的？（变体：还有什么形状也可以？）

拆解与思考

核心答案：圆形是等宽曲线——任意方向的宽度相同，井盖不会掉入井口。

额外优点：

1. 受力均匀，不易碎裂。
2. 搬运方便——可滚动。
3. 旋转对称，盖上不需对齐方向。
4. 钻挖设备天然旋转切削出圆形截面。

答案

圆形是等宽曲线。还可以是任何等宽曲线，如 Reuleaux 三角形（鲁洛克斯三角形）。

延伸

Reuleaux 三角形：以等边三角形三个顶点为圆心、边长为半径画三段圆弧组成的"曲边三角形"。也是等宽曲线，理论上也能做井盖。

应用：转子发动机（马自达 RX-8）、特殊钻头、比特币造型。

---

题目 15：1000 瓶药水找毒药

题面

1000 瓶药水中 1 瓶有毒。毒发时间 24 小时。你有 10 只小白鼠和 24 小时时间。如何找出毒药？

拆解与思考

朴素思路：每只鼠试一瓶 → 最多检测 10 瓶。

关键洞察——二进制编码：

1000 瓶药水编号 1-1000，转为二进制（最多 10 位）。

让第 i 只小白鼠喝所有"二进制第 i 位为 1"的药水。

24 小时后：

• 第 i 只鼠死 ⇔ 毒药的第 i 位是 1。
• 10 只鼠的生死组成一个 10 位二进制数，即毒药编号。

2¹⁰ = 1024 ≥ 1000，所以 10 只鼠足够。

答案

10 只鼠足够。把药水按 1-1000 编号，二进制编码后让每只鼠喝对应位为 1 的所有药水。24 小时后生死的二进制模式给出毒药编号。

例子

若 1, 3, 5, 7, 9 号鼠死（10 位二进制 1010101010），毒药编号 = 2⁹+2⁷+2⁵+2³+2¹ = 512+128+32+8+2 = 682。

延伸

信息论下界：1000 种可能需要 ⌈log₂1000⌉ = 10 bit 信息。每只鼠提供 1 bit（生/死），所以至少需要 10 只鼠。这是最优解。

工程意义：群组测试（Group Testing）——在大量样本中找少数"阳性"样本，可用于病毒检测、质量控制、信道编码。

---

题目 16：跳棋拿硬币

题面

10 枚硬币排成一排。两人轮流取 1 枚或 2 枚相邻硬币（不能隔空取，取后硬币分成独立的两段）。取到最后一枚硬币者胜。先手必胜还是后手必胜？

拆解与思考

对称策略：

n=1: 先手取走，胜。 n=2: 先手取 2，胜。 n=3: 先手取 1，剩 2 段（1+1），后手取 1 段的 1 枚，先手取另 1 段的 1 枚，胜。 n=4: 先手取中间 2 枚，剩两段（2+0+2？不对）。重新分析：

取 2 枚相邻 → 剩 2 枚相邻。后手取走 → 后手胜。 取中间 1 枚 → 剩 1+1+1+1（断裂成 2 段各 1，中间分开）。后手取 1 段 → 先手取另一段 → 先手胜。

仔细看：n=4 时，先手取中间 1 枚（位置 2 或 3），剩 1+1 的两段（外侧 1 枚 + 内侧 1 枚 + 外侧 1 枚？不对）。

让我重新画：

位置：1 2 3 4
硬币：A B C D

取中间 B：剩 A _ C D，即 A 孤立 + CD 相邻两段。 后手取 A：剩 CD，先手取 CD → 先手胜。 后手取 CD 中 1 枚：剩 A + 剩 1 枚。先手取 A，后手取最后 1 枚 → 后手胜。

所以先手取 B 不一定胜。

正确策略——对称：

n=4：先手取中间 2 枚（BC）→ 剩 A 和 D 两段独立。后手只能取一段的 1 枚，先手对称取另一段。先手胜。

n=10：先手取中间 2 枚（位置 5, 6）→ 剩 4+4 两段对称。之后每次后手取 X 枚，先手在对称位置取 X 枚。先手必胜。

答案

先手必胜。第一步取中间 2 枚（n=10），之后对称模仿后手。

延伸

通用结论：n 偶数时先手必胜（取中间 2 枚，对称）。n 奇数时先手胜（取中间 1 枚，对称）。

实际上，所有这种"对称游戏"先手都有必胜策略（除非有特殊禁手）。

---

解题模板（总结）

通用流程

1. 先确定理论下界（信息论下界、分组下界）。
2. 尝试构造达到下界的方案。
3. 如果达不到下界，分析差距在哪里。
4. 对于"最少几次"的问题，利用 log₃（天平）或分组思想。
5. 对于"能否做到"的问题，先判断可行性再动手。
6. 对经典题要背答案但理解推理——面试官会追问变形。

信号清单

题面信号	推理工具
"最少几次 / 最少多少分钟"	信息论下界 / 贪心策略
"天平称重"	三分查找 / 信息熵最大化
"能否做到 / 多少时间"	先判断可行性
"如何分配 / 投票"	逆向归纳 / 博弈论
"缩放 / 大小变化"	缩放规律（L² vs L³）
"灯泡开关 / 因子"	数论（完全平方数）
"圆桌 / 棋盘对称"	对称策略
"二进制 / 检测"	二进制编码
"时间 / 时针"	相对速度 / 周期

常见陷阱

• 不先算下界：上来就构造方案，可能错过最优解。
• 二分滥用：天平每次三结果，应该用三分而非二分。
• 忽视对称：很多游戏有对称必胜策略。
• 被表面规则束缚：题目没说不允许的事，就可以做（如利用温度）。
• 不识别陷阱题：有些任务不可能完成，要敢说"做不到"。
• 背答案不理解：面试官变形后无法应对。

面试策略

1. 听题后停 5 秒——确认理解题意。
2. 复述题目——避免误读。
3. 先说思路——再动手算。
4. 指出关键洞察——让面试官知道你看懂了题。
5. 承认不知道——遇到没见过的题，诚实说，从基本原理推导。
6. 追问变形——主动问"如果 N 不同呢？"

延伸阅读

书籍

• 《Are You Smart Enough to Work at Google?》— William Poundstone
• 《How Would You Move Mount Fuji?》— Rick Michaelson，微软面试题集
• 《Heard on the Street》— Timothy Crack，量化面试题
• 《Cracking the Coding Interview》— Gayle McDowell，附智力题章节

在线资源

• 25 Horses Problem 详解
• Google Interview Questions Archive
• Brainstellar Interview Puzzles
• TechInterview Puzzles