绿皮书里的智力面试题

题目来源：《A practical Guide to quantitative finance interviews》，解答和书上的可能不一样。

1. A 让 C 要送一份资料给 B。但 C 不可靠， A 可以把资料放在盒子里锁上才能送给 B ，但 B 也需要拿到钥匙才能打开盒子。问 A 有方法将资料安全送达 B 处吗？

2. 房间里有一盏灯。房间外有四个开关，但只有一个开关是控制灯泡。现在四个开关都处于关闭状态。问能否只进入房间一次，就能找出控制灯泡的开关。

3. 在一个黑房间里有 100 枚硬币，其中 20 枚正面朝上，其它的反面朝上。你看不到各枚硬币的朝向，也不允许以任何形式来分辨它，但允许你对它们进行翻转（在不知朝向的情况下）。问你是否可能将这些硬币分成两堆，这两堆硬币有相同多的正面朝上的硬币。

4. 三袋水果，其中一袋里面是苹果，第二袋是桔子，第三袋既有苹果也有桔子。在袋子外面有标签标明袋子的内容。但不幸的是，你被告知三个袋子的标签都被标错了。你现在可以从袋子里拿出水果来分辨袋子。问：你至少需要拿出几个水果，才能更正这三个袋子的标签？

5.  监狱里关了 50 个囚犯。监狱长有一个硬币，现在正面朝上。每分钟监狱长会叫入一个囚犯。这个囚犯可选择翻转硬币或者不翻转。如果有囚犯宣布每个囚犯都被叫入至少一次，并且情况确实如此，那么所有囚犯都会被释放；如果出现错误，那么所有囚犯都会被处死。囚犯在关入单人监狱之前可以商议策略，但之后不能有任何交流。问囚犯能达成策略吗？

6. 1 只钟从墙上摔下来，裂成三个完整的碎片。我们发现三碎片上数字之和相同。问各碎片上的数字。

7. 手头有 98 个不同的整数，取值范围为 1 到 100。问如何快速找到两个缺失的数。

8. 10 个袋子里分别有 100 枚硬币。其中 9 个袋子里的硬币是一样重的，每个硬币都是 10 克。另外一个袋子里硬币也都是一样，但重量都是 9 克或者都是 11 克。问怎么只用一次带刻度的电子秤分辨出与众不同的袋子以及具体的重量。

9. 五个袋子里分别有 100 枚硬币。每个袋子里的硬币都是一样的，但不同袋子的硬币可能不一样，可能有三种重量，分别为 9 克、10 克和 11 克。问至少需要使用几次带刻度的电子秤才能分辨出每个袋子的硬币重量？

10. 一个与世隔绝的岛屿上有 13 个黑人、15 个白人和 17 个黄种人。任何两种不同皮肤的人遇到一起，就会都变成另外一种颜色。问是否可能所有人都变成同一种颜色？

11. 你有 100 个硬币。首先你将它分成两堆，分别有 x 枚和 y 枚硬币，得到它们的乘积。再任意将其中的一堆分成两堆，得到两个小堆的硬币数量的乘积。这样一直分下去直到每个堆只有一枚硬币无法再分为止。将所有得到的乘积加起来，问最后这样的乘积和最大是多少？

12. 一个 6×8 的棋盘，你需要逐步将其分拆成小方块。你每次可以选择其中的一块，沿着方块边界将它分成两部分，比如你开始将 6×8 的棋盘分成一个 6×3 和一个 6×5 的小棋盘。问你至少需要分多少次，才能将棋盘分成 48 块小方格。

13. 一个单向的环形跑道上有 100 个随机分布的加油站，每个加油站里有油，合计起来恰好够汽车跑一个整圈。你有一辆汽车，刚开始时汽车油箱是空的，但一遇到加油站就可以加油。问你是否总是可以选择合适的出发点，使得汽车能够跑完一圈？

14. 监狱里有 7 名囚犯。监狱长给这些囚犯每人都带了个帽子，共有七种颜色（分别为彩虹七色）。各个囚犯都能看到其它人的帽子颜色，但看不到自己头上的帽子。之后监狱长让囚犯猜测自己头上的帽子颜色。只要有一人猜对，所有囚犯都会被释放。如果所有人都猜错了，所有囚犯都会被处死。囚犯不能听到其它人的猜测且不能互相交流。问囚犯可以使用什么策略，最大化被释放的概率？

1. A 将盒子加锁寄给 B ， B 再加一把锁送还给 A ， A 将自己的锁取下后再送给 B。

2. 假设开关编号为 1、2、3、4。那么首先打开 1 和 2 ，开 1 分钟；然后关掉 2 ，打开开关 3。迅速进入房间，摸一摸灯泡的热度。如果灯泡是热的，并且灯是亮的，那么答案是 1 ；如果灯泡是热的，灯是熄的，那么答案是 2 ；如果灯泡是冷的，并且灯亮着，那么答案是 3 ；否则答案是 4。

3. 先随便将硬币分为两堆，其中一堆是 20 枚，另一堆为 80 枚。然后翻转第一堆所有硬币。

4. 根据已知条件，三个袋子的标签都被标错了，那么正确标签只有两种可能性。只需要从目前标记为混合水果的口袋拿出一个水果，根据这个水果的种类就能区分这两种可能性。

5. 这个题目有一个隐含的假设，即每个人都无限次甚至随机地被叫入。在这种情况下，任选一人作为观察者，当碰到硬币正面朝下时则翻转硬币，否则什么都不做。其余每个囚犯在被叫入时如果硬币正面朝上则翻转硬币，，而且这 49 个囚犯只在第一次碰到这种情况时进行操作，其它情况什么都不做。这样当观察者翻了 49 次硬币之后，他可以确定其余 49 个囚犯都被叫入过。

6. 关键是注意 1 和 12 是连续的，剩下就简单了。

7. 计算 98 个数的和与 1 到 100 的和的差，即为缺失的两个数的和；计算 98 个数的平方和与 1 到 100 的平方和的差，即为缺失的两个数的平方和；剩下来的工作是解一个两元方程。

8. 从第 i 个袋子里取出 i 枚硬币，放在一起秤。其重量与 450 的差即使与众不同的袋子的编号，重量大于 0 表示该袋子里的硬币重 11 克，否则重 9 克。

9. 从第 i 个袋子里取出 3^(i-1)枚硬币，一起秤重量。不妨设硬币的重量分别为 0 克、1 克和 2 克。接下来即秤出的重量的三进制表示问题。

10. 不能。假设有 x 个白人、y 个黑人和 z 个黄种人，那么 y+2z 被 3 除的余数是一个不变量。刚开始等于 1 ，它不可能变成 0。

11. 100×99/2 = 4950。无论怎么分，最后得到的值都是对数。即任何两个硬币，它们恰好在其中某次被分开并被统计一次。

12. 每分一次碎片数量增加 1。一开始是 1 块，最后是 48 块。故恰好需要分 47 次。

13. 假设加油站的油量分别是 y1, y2, ..., y100 ，距离下一个加油站的距离是 z1, z2, ..., z100。令 xi = yi - zi。那么题目所需要的是证明一定存在某个开始位置，使得从该位置开始的任何长度的连续 xi 序列之和都大于 0。我们先取出和最小的连续一段 xi ，那么从这一段的下一个加油站开始即可。如果该加油站不满足要求的话，从该加油站开始还有和小于 0 的连续段，这与它前面的和最小的连续段加起来可得到和更小的一段，矛盾。

14. 假设帽子颜色标号为 0 到 6。 第 n 名囚犯回答自己的帽子颜色为 n 减去他看到的其他囚犯的帽子颜色之和，然后再被 7 除的余数。假设 7 个人的帽子颜色之和被 7 除的余数为 k ，那么第 k 名囚犯一定答对了。

Q. E. D.