Brain Teasers & Game Theory 面试题全集

来源：Two Sigma 面经（192条）+ Citadel 面经（244条）+ 绿皮书（Chapter 2 Brain Teasers）

（共 20 道题，2 大分类，覆盖绿皮书 Chapter 2 的博弈论与逻辑推理核心题目 + Two Sigma 和 Citadel 面经中的 brain teaser 题目。）

频率标准：

• ⭐⭐⭐⭐⭐：必考核心题，多家公司反复出现（5+ 次），面试重中之重
• ⭐⭐⭐⭐：高频题，经常出现在面试中（3-4 次）
• ⭐⭐⭐：中频题，多次出现或作为重要知识点（2-3 次）
• ⭐⭐：偶尔出现或作为追问
• ⭐：罕见但可能出现，或作为加分题

---

一、博弈论与策略（Game Theory）

知识点

Backward Induction（逆向归纳）

从结局往前推。先想”如果只剩最后一步会怎样”，然后”倒数第二步会怎样”……一直推回起点。

适用场景： 多人轮流决策，每人理性且想最大化自己的利益。

---

例题

题目49：Screwy Pirates（海盗分金）⭐⭐⭐⭐⭐

来源： 绿皮书 2.1 + Citadel 面经

5 个海盗（A 最高级到 E 最低级）分 100 金币。规则：最高级的提方案，所有人投票，≥ 50% 同意就通过（提议者也投票），否则提议者被杀，下一个人提方案。每个海盗：首先想活命，其次想要更多金币，最后想杀人。

A 应该怎么提方案？

答案： A 提 98 : 0 : 1 : 0 : 1（A 拿 98，C 拿 1，E 拿 1）

解法（绿皮书，Backward Induction，一步步来）：

如果只剩 2 个人（D 和 E）： D 提 100:0。D 自己投赞成（1/2 = 50%），通过。E 什么都拿不到。

如果剩 3 个人（C, D, E）： C 知道如果自己被杀，D 会拿 100，E 拿 0。所以 C 给 E 1 个金币（比 E 在 D 的方案中拿到的 0 多），E 会投赞成。C 提 99:0:1。C + E = 2/3 > 50%，通过。

如果剩 4 个人（B, C, D, E）： B 知道如果自己被杀，C 拿 99，D 拿 0，E 拿 1。B 给 D 1 个金币（比 D 在 C 方案中拿到的 0 多），D 投赞成。B 提 99:0:1:0。B + D = 2/4 = 50%，通过。

5 个人（A, B, C, D, E）： A 知道如果自己被杀，B 拿 99，C 拿 0，D 拿 1，E 拿 0。A 需要 3 票（包括自己）。给 C 1 个金币（比 C 在 B 方案中拿到的 0 多），给 E 1 个金币（比 E 在 B 方案中拿到的 0 多）。C 和 E 投赞成。

A 提 98:0:1:0:1。A + C + E = 3/5 > 50%，通过。

面试关键： 向面试官展示你从简单情况开始推，逐步增加复杂度。

---

题目50：Tiger and Sheep（老虎和羊）⭐⭐⭐

来源： 绿皮书 2.1 + Citadel 面经

100 只老虎和 1 只羊在岛上。老虎更喜欢吃羊，但吃了羊会变成羊（会被其他老虎吃）。所有老虎完全理性，首先想活命。羊会被吃吗？

答案： 不会（100 是偶数 → 羊安全）

解法（绿皮书，从小情况推）：

1 只老虎： 吃。吃完变成羊，但没有其他老虎了，安全。

2 只老虎： 不吃。如果一只吃了变成羊，另一只会吃它（变成 1 只老虎的情况）。所以谁也不敢吃。

3 只老虎： 吃。吃完变成 2 只老虎 + 1 只羊。2 只老虎不敢吃（上面分析了），所以变成羊是安全的。

4 只老虎： 不吃。吃完变成 3 只老虎的情况，3 只老虎会吃，所以不安全。

规律： 奇数只老虎 → 吃。偶数只 → 不吃。100 是偶数 → 不吃。

直觉： 偶数只老虎形成了一种”恐怖平衡”——每只都想吃，但谁先动谁就变成被吃的。就像冷战中的核威慑。

---

题目51：Secretary Problem（最优停止）⭐⭐⭐

来源： Citadel 面经

$N$ 个候选人依次面试。每次看完必须立刻决定录不录（不能回头看之前的人）。怎么最大化录到最好的那个人的概率？

答案： 前 $N/e \approx 37\%$ 个人全部拒绝（只观察），之后录取第一个比之前所有人都好的。

成功概率 $\approx 1/e \approx 36.8\%$

解法思路：

设阈值为 $r$（前 $r$ 个人全拒绝）。最佳候选人在位置 $i$（$i > r$）且被录取的条件是：前 $i-1$ 个人中最好的在前 $r$ 个里。

\[P(\text{成功}) = \sum_{i=r+1}^{N} P(\text{最佳在位置}i) \times P(\text{前}i-1\text{个最好的在前}r\text{个}) = \sum_{i=r+1}^{N} \frac{1}{N} \times \frac{r}{i-1}\] \[= \frac{r}{N} \sum_{i=r+1}^{N} \frac{1}{i-1} \approx \frac{r}{N} \ln\frac{N}{r}\]

对 $r/N$ 求导令其为零，得 $r/N = 1/e$，最优概率 = $1/e$。

---

题目52：猜 2/3 of Average ⭐⭐⭐⭐

来源： Citadel 面经

$N$ 个人各猜 1-100 的数。最接近所有人平均值的 2/3 的人赢。最优策略？

答案： Nash 均衡是所有人猜 1。

推理过程：

• 如果大家都猜 50 → 2/3 × 50 = 33 → 应该猜 33
• 如果大家都猜 33 → 2/3 × 33 = 22 → 应该猜 22
• 如果大家都猜 22 → 2/3 × 22 = 15 → 应该猜 15
• ……不断迭代，最终趋向 1

面试中说： “通过反复迭代 best response，最终收敛到所有人猜 1 的 Nash 均衡。”

---

题目53：Two Envelopes Paradox ⭐⭐

来源： Citadel 面经

两个信封，一个是另一个的 2 倍钱。你打开一个看到 100。换的期望 = $0.5 \times 50 + 0.5 \times 200 = 125 > 100$，所以换？但对方也这么想，永远在换？

答案： 这是一个悖论。错误在于：你不能同时假设 $P(\text{大信封}) = P(\text{小信封}) = 0.5$ 对所有金额成立。

正确分析需要指定先验分布。 如果你知道金额是从某个分布里抽的，用贝叶斯就能正确分析。悖论产生于使用了不正当的”均匀先验”（不存在对所有正实数均匀的分布）。

面试中说： “The paradox arises from an improper prior. To resolve it, we need to specify a proper prior distribution for the amounts.”

---

二、Brain Teasers（逻辑推理题）

知识点

Brain teasers 不需要高深数学，考的是：

1. 简化问题： 从小例子开始找规律
2. 逻辑推理： 一步步推导
3. 跳出框架： 不走寻常路
4. 对称性和不变量： 找到在变化过程中不变的量

---

例题

题目54：River Crossing（过桥）⭐⭐⭐

来源： 绿皮书 2.2

4 人过桥，1 个手电筒，桥最多走 2 人（按慢的人速度走）。速度：A=10分钟，B=5分钟，C=2分钟，D=1分钟。最快多久全过？

答案： 17 分钟

解法（绿皮书）：

关键洞察（绿皮书高亮）： 10 分钟的人和 5 分钟的人应该一起过（这样只浪费 10 分钟而不是 10+5=15 分钟分开过）。但这不应该在第一轮，否则没人送手电筒回来。

最优策略：

1. C(2) 和 D(1) 过 → 2 分钟。D 送手电筒回来 → 1 分钟。（累计 3 分钟）
2. A(10) 和 B(5) 过 → 10 分钟。C 送手电筒回来 → 2 分钟。（累计 15 分钟）
3. C(2) 和 D(1) 过 → 2 分钟。（累计 17 分钟）

为什么不能更快？ 最慢的两人（A=10, B=5）必须过桥。如果分开过需要 10+5+回程 = 17+。让他们一起过只花 10 分钟（B 被 A 的速度”免费”带过去了）。

---

题目55：Burning Ropes（烧绳子）⭐⭐⭐⭐⭐

来源： 绿皮书 2.2 + Two Sigma + Citadel

两根不均匀绳子各烧完 1 小时。量出 45 分钟。

答案：

1. 同时点：绳 1 两头 + 绳 2 一头
2. 绳 1 两头烧完 → 30 分钟（两头同时烧，总时间减半）
3. 此时绳 2 还能烧 30 分钟。立刻点绳 2 的另一头
4. 绳 2 两头都在烧 → 再过 15 分钟烧完
5. 总共 30 + 15 = 45 分钟

关键洞察（绿皮书）： 一根绳子两头同时烧，烧完时间 = 原来的一半。虽然绳子不均匀（有的地方快有的慢），但两头同时烧保证了总时间减半。

---

题目56：Defective Ball（12 球问题）⭐⭐⭐

来源： 绿皮书 2.2

12 个球，1 个有问题（不知道比正常的重还是轻）。天平称 3 次，找出问题球并判断轻重。

解法（绿皮书，决策树）：

第 1 次： 4 vs 4（剩 4 个不上秤）

如果平衡： 问题球在剩下 4 个中。

• 第 2 次：3 个嫌疑球 vs 3 个正常球
  • 平衡 → 第 4 个是问题球，第 3 次和正常球比确定轻重
  • 不平衡 → 标记”疑似重”或”疑似轻”，第 3 次两两比较确定

如果不平衡： 标记一边为”疑似重”（4 个），另一边为”疑似轻”（4 个）。

• 第 2 次：混合称（从疑似重中取 2 个 + 疑似轻中取 1 个 vs 正常球 3 个），通过结果缩小范围
• 第 3 次：最终确定

一般化（绿皮书）： 如果已知轻重，$n$ 次称量可以找出 $3^n$ 个球中的问题球。如果不知道轻重，$n$ 次可以找出 $(3^n - 3)/2$ 个球中的问题球。

---

题目57：Horse Race（赛马）⭐⭐⭐⭐

来源： 绿皮书 2.2

25 匹马，5 条跑道（无计时器），最少几场找最快的 3 匹？

答案： 7 场

解法（绿皮书）：

前 5 场： 分成 5 组各 5 匹，每组跑一场。得到每组的排名。

设 5 组的冠军分别是 $a_1, b_1, c_1, d_1, e_1$（组内排名最好的）。

第 6 场： 5 个冠军比赛。假设结果是 $a_1 > b_1 > c_1 > d_1 > e_1$。

分析：

• $a_1$ 确定是全场第 1。
• $d_1, e_1$ 的组全部淘汰（他们的冠军都排不进前 3，组内其他马更不行）。
• $c_1$ 组只有 $c_1$ 自己可能是前 3（$c_1$ 最多第 3，$c_2$ 就不行了）。
• $b_1$ 组有 $b_1, b_2$ 可能是前 3。
• $a_1$ 组有 $a_2, a_3$ 可能是前 3（$a_1$ 已确定第 1）。

第 7 场： $a_2, a_3, b_1, b_2, c_1$ 这 5 匹比赛。前 2 名就是全场第 2 和第 3。

---

题目58：Coin Piles（硬币分堆）⭐⭐⭐

来源： 绿皮书 2.4

1000 枚硬币在桌上，980 反面朝上，20 正面朝上。你被蒙眼（看不到也摸不出正反）。把硬币分成两堆，使两堆正面数相同。

答案： 随便拿 20 枚出来成一堆，全部翻转。

解法（绿皮书）：

假设你拿出的 20 枚里有 $k$ 枚正面朝上（$0 \leq k \leq 20$）。

翻转前：

• 这堆有 $k$ 枚正面
• 另一堆有 $20 - k$ 枚正面

翻转后：

• 这堆的 $k$ 枚正面变反面，$20-k$ 枚反面变正面 → 正面数 = $20 - k$
• 另一堆还是 $20 - k$ 枚正面

$20 - k = 20 - k$ ✓ 两堆正面数相等！

不管 $k$ 是多少都成立。 这就是对称性的力量。

---

题目59：Last Ball（最后一个球）⭐⭐⭐

来源： 绿皮书 2.3

20 蓝球 + 14 红球。每次取 2 个：同色放回 1 蓝球，异色放回 1 红球。最后一个球什么颜色？

答案： 蓝色

解法（绿皮书，找不变量）：

每次操作红球数量的变化：

• 取 2 蓝 → 放回 1 蓝 → 红球不变（变化 0）
• 取 2 红 → 放回 1 蓝 → 红球减 2（变化 -2）
• 取 1 蓝 1 红 → 放回 1 红 → 红球不变（变化 0）

不变量：红球数量的奇偶性不变。 每次变化 0 或 -2（偶数）。

初始红球 = 14（偶数）→ 最终红球也是偶数 → 最小的非负偶数 = 0 → 最后一个球是蓝色。

---

题目60：Chameleon Colors（变色龙）⭐⭐⭐

来源： 绿皮书 2.7

岛上 13 红、15 绿、17 蓝变色龙。两只不同色相遇，都变成第三种颜色。能否全变同色？

答案： 不能

解法（绿皮书，Modular Arithmetic 不变量）：

每次相遇：一种颜色 -2，另两种各 +1。三种数量的两两之差变化：

初始差：$15 - 13 = 2$，$17 - 15 = 2$，$17 - 13 = 4$

每次操作后，任意两种数量的差变化 $\pm 3$ 或 $0$。所以 差 mod 3 不变。

初始差 mod 3：$2 \mod 3 = 2$

全同色需要差 = 0，即 $0 \mod 3 = 0 \neq 2$。所以不可能。

---

题目61：Mislabeled Bags（标签全错的袋子）⭐⭐⭐

来源： 绿皮书 2.4

三个袋子标着”苹果”、”橘子”、”混合”。所有标签都贴错了。 最少取几个水果确定所有袋子的真实内容？

答案： 1 个

解法（绿皮书）：

从标着”混合”的袋子取 1 个水果。因为标签全错，这个袋子不是混合的，只能是纯苹果或纯橘子。

• 如果取出苹果 → 这袋是苹果。标着”橘子”的不能是橘子（标签全错），也不是苹果（已确定），所以是混合。剩下标着”苹果”的是橘子。
• 如果取出橘子 → 同理推导。

关键： “标签全错”这个信息非常强——排除了很多可能性。只需要 1 个数据点就能确定一切。

---

题目62：Light Switches（灯泡开关）⭐⭐

来源： 绿皮书 2.3

门外 4 个开关，屋内 1 个灯泡。只能进屋一次。怎么确定哪个开关控制灯泡？

答案：

1. 开关 1 打开，等 10 分钟
2. 关掉开关 1，打开开关 2
3. 进屋：
   • 灯亮 → 开关 2
   • 灯灭但灯泡热 → 开关 1（刚才开了 10 分钟）
   • 灯灭且灯泡冷 → 开关 3 或 4（需要额外信息区分）

关键（绿皮书）： 利用灯泡的温度作为额外信息维度。不只是看”亮/灭”（1 bit），还看”热/冷”（多 1 bit），所以能区分更多情况。

---

题目63：Infinite Power Tower ⭐⭐

来源： 绿皮书 2.2

$x^{x^{x^{\cdots}}} = 2$，求 $x$。

答案： $x = \sqrt{2}$

解法（绿皮书）：

设无穷塔 = $y$，则：

\[\underbrace{x^{x^{x^{\cdots}}}}_{n \text{ terms}} = y \quad \text{当 } n \to \infty\]

加一层 $x$ 不影响结果（因为已经是无穷了）：

\[x^{\underbrace{x^{x^{\cdots}}}_{n \text{ terms}}} = x^y = y\]

所以 $x^y = y$。已知 $y = 2$：$x^2 = 2 \Rightarrow x = \sqrt{2}$。

---

题目64：Calendar Cubes（日历骰子）⭐⭐

来源： 绿皮书 2.3

设计两个骰子，能显示 01-31 的所有日期（每个日期用两个骰子并排显示）。

答案：

• 骰子 1：0, 1, 2, 3, 4, 5
• 骰子 2：0, 1, 2, 6, 7, 8

解法（绿皮书）：

• 两个骰子都要有 0（01-09 需要）、1（11, 1x 需要）、2（22, 2x 需要）
• 剩余数字 3-9 有 7 个，但只有 6 个空位（每个骰子 3 个空位）
• 关键：6 翻转可以当 9 用！ 所以实际只需要分配 3, 4, 5, 6, 7, 8 六个数字到 6 个空位

---

题目65：Poisonous Wine（毒酒）⭐⭐⭐

来源： 绿皮书 7.2 + Citadel 面经

1000 瓶酒有 1 瓶有毒。有 10 个试毒者。24 小时后毒发。怎么 1 轮找出毒酒？

答案： 二进制编码

$2^{10} = 1024 > 1000$。给每瓶酒编号 0-999（二进制表示，10 位）。

第 $i$ 个试毒者喝所有编号的第 $i$ 位是 1 的酒。

24 小时后，死亡的试毒者编号组成一个 10 位二进制数 = 毒酒的编号。

例子： 酒 #5 = 0000000101（二进制）。第 1 和第 3 个试毒者会喝到。如果恰好是这两人死了，毒酒就是 #5。

信息论角度： 10 个试毒者，每人两种状态（活/死），总共 $2^{10} = 1024$ 种结果，足够区分 1000 瓶酒。

---

题目66：Quant Salary（算平均工资）⭐⭐

来源： 绿皮书 2.3

8 个 quant 想知道他们的平均工资，但没人愿意透露自己的工资。怎么办？

答案：

1. 第 1 个人想一个随机大数 $R$，把 $R +$ 自己的工资传给第 2 个人
2. 第 2 个人加上自己的工资，传给第 3 个人
3. ……
4. 第 8 个人加完后把总数传回第 1 个人
5. 第 1 个人减去 $R$，除以 8 = 平均工资

没有任何人知道其他人的工资，但每个人都知道了平均工资。

---

题目67：Door to Offer（两扇门两个守卫）⭐⭐

来源： 绿皮书 2.3

两扇门（一扇通 offer，一扇通出口）。两个守卫（一个永远说真话，一个永远说假话）。你可以问一个守卫一个 yes/no 问题。怎么找到 offer 的门？

答案： 问任一个守卫：”如果我问另一个守卫哪扇门通 offer，他会说什么？” 然后选相反的门。

为什么？

• 如果你问的是真话守卫：他会如实告诉你假话守卫的回答（错误答案）→ 你选反的 ✓
• 如果你问的是假话守卫：他会谎报真话守卫的回答（把正确答案变成错误）→ 你选反的 ✓

两种情况你都选反的，都能找到正确的门。

---

题目68：Message Delivery（安全传信）⭐⭐

来源： 绿皮书 2.3

通过不可信的信使传递文件。你和收件人各有自己的锁和钥匙（但不能共享钥匙）。怎么安全传递？

答案：双锁协议

1. 你把文件放进箱子，用你的锁锁上，寄出
2. 收件人收到后，加上他的锁（现在箱子有两把锁），寄回
3. 你收到后，用你的钥匙开你的锁（只剩收件人的锁），寄出
4. 收件人用他的钥匙开锁，拿到文件

全程没有交换钥匙，信使打不开箱子。

---