绿皮书刷题记录_01
条评论《A Practical Guide to Quantitative Finance Interviews》（俗称绿皮书）是一本经典的量化笔面试指南，内含大量量化笔面试中的真题。尽管这一本书在2008年即出版，但如今国内很多量化私募笔面试中仍包含与书内相同或相似的题目。因此若要准备量化笔面，这本书必不可少。
互联网上关于这本书的整理已经很丰富了，因此这一系列文章并不会对书中问题进行全盘整理，而是挑出部分题目进行整理。挑选标准大致如下：
- 书中对题目解答不够完善的；
- 有自己额外思考探索的；
- 解法不易记忆，需要记录下来复习的。
那么，让我们开始吧！
River Crossing
Four people, A, B, C and D need to get across a river. The only way to cross the river is by an old bridge, which holds at most 2 people at a time. Being dark, they can’t cross the bridge without a torch, of which they only have one. So each pair can only walk at the speed of the slower person. They need to get all of them across to the other side as quickly as possible. A is the slowest and takes 10 minutes to cross; B takes 5 minutes; C takes 2 minutes; and D takes 1 minute.
What is the minimum time to get all of them across to the other side?
首先考虑一共需要多少次过桥。很显然，由于有 4 个人，而除了第一次过桥以外，每次都需要有一个人折返回来送火把，因此总共需要三次过桥，中间穿插两次折返。
由于 D 的过河速度最快，因此很容易想到的思路是全程让 D 左右运送 A、B 和 C 过桥。然而这意味着 A 和 B——两位最慢的人的过桥时间将叠加，无法达到最优。因此，要尽量令 A 和 B 同时过桥。
然而在这种策略下，不可能让 B 先过桥，再单独回来，再接上 A 过桥——这样实际上 B 要过三次桥，没有达到我们的目的。因此最好的策略下，应该完成 A 和 B 一次性过桥的目的。
继续考虑：A 和 B 这一组合应该什么时候过桥呢？如果 A 和 B 是第一组过桥，那么 A 或者 B 还是需要回来一趟，显然不可取。那么如果 A 和 B 作为第三组过桥，那么第二次折返时由谁折返传递火把？显然也不现实。那么唯一的解就在于，A 和 B 作为第二组过桥。那么显然，第一组和第三组都只能是 C 和 D（尽可能减少 A 和 B 的行动）。
现在考虑折返的情况。显然 C 和 D 都需要折返一次。那么对于两次折返，二者的顺序无关紧要，因为并不会影响总时间。
1 | A, B, C, D Left ---------------- Right |
总时长：$2+1+10+2+2=17$。
Burning Ropes
You have two ropes,each of which takes 1 hour to burn. But either rope has different densities at different points,so there’s no guarantee of consistency in the time it takes different sections within the rope to burn. How do you use these two ropes to measure 45minutes?
这类题目非常经典也烂大街，但是每次都忘记怎么解。
关键问题在于，在一根绳子的总燃烧时间是一小时的情况下，如何同一根绳子刻画其他的时间长度？
答案是，从绳子两边同时开始燃烧，这样可以保证绳子烧完时用时刚好半小时。
这道题的解答需要用到两次这一性质。一开始先将绳子 A 从一端开始燃烧，绳子 B 从两端同时开始燃烧。当绳子 B 燃烧结束时，绳子 A 还剩半小时。此时从另一端开始燃烧绳子 A，则剩下的时间刚好 15 分钟。
稍微扩展一下：两根这样的绳子，可以衡量哪些时长的时间？答案是 15 分钟、30 分钟、45 分钟、1 小时、1 小时 30 分钟、2 小时。
Defective Ball
You have 12 identical balls. One of the balls is heavier OR lighter than the rest (you don’t know which). Using just a balance that can only show you which side of the tray is heavier, how can you determine which ball is the defective one with 3 measurements?
从信息论的角度来看，这道题意味着：每一次测量都给出三种状态：大于、小于和等于。而若要用这三种状态来进行编码，能够覆盖的可能性数量为 $3^3=27$ 种。由于这道题中只有 12 颗球，且不一致的那颗球要么轻了要么重了，因此一共存在 $12\times2=24$ 种情况，因此理论上 3 次测量是有可能找出不同的那颗球，并判断其是轻是重的。
那么从这个角度来看，每次测量都应当尽可能使得可能的情况数量坍缩到原来的 $1/3$。譬如说刚开始我们平均分为三组 A、B、C，则存在6种等可能的情况：A 重、A 轻、B 重、B 轻、C 重、C 轻。假设第一次比较 A 和 B 的重量，无论结果如何，都只会剩下两种等可能的情况：
| 结果 | 剩余的可能情况 |
|---|---|
| $A=B$ | C 重、C 轻 |
| $A>B$ | A 重、B 轻 |
| $A < B$ | A 轻、B 重 |
考虑 $A=B$ 的情况，此时特殊的球必然在 C 中，存在 8 种情况。如果将 C 分为两组比较？那么情况将坍缩为原来的 $1/2$，究其原因在于“相等”这一结果先验不可能发生。这种情况下，仍然剩下 4 种情况，不可能找出答案。那么需要效仿第一次测量的方式，留下一颗球（如果留下两颗球，仍然可能剩余 4 种情况），剩下的 3 颗球其中两颗分为一组，另一颗与 A 或 B 组中的一颗球分为一组（注意此时已经知道 A 和 B 中都是正常球）。无论这一测量结果如何，都只剩下不到 3 种情况，剩下过程这里不展开。
接下来，考虑 $A>B$ 的情况（$A<B$ 的情况类似）。下一步我们选取球来测量的原则是，必须要同时拥有产生三种结果（即大于、小于和相等）的可能，且无论我们得到什么什么结果，都必须使得可能情况坍缩至不多于 3 样（这意味着，也不能少于 2 样）。因此我们很容易排除以下策略：
| 在剩下的球中选取测量的球数 | 排除原因 |
|---|---|
| 8 | 不可能产生“相等”这一情况 |
| 7 | 若相等，则仅剩下 1 种情况 |
| 小于或等于 4 | 若相等，则剩下多于 3 种情况 |
这样看来，我们要么选 5 个球来比较，要么选 6 个球来比较。从实践的角度来看，我们是没有被禁止在比较过程中加入 C 组正常球的，下文具体分析。
若选择 6 个球来比较，无外乎 6 种方法，其它方法都与其中一种等价或类似：
| 选取方式 | 分析 |
|---|---|
| （A1、A2、A3）vs（B1、B2、B3） | 不存在“相等”的可能性，排除 |
| （A1、A2、B3）vs（B1、B2、A3） | 如果 $A>B$，则剩下 4 种情况，排除 |
| （A1、A2、B1）vs（A3、A4、B2） | 无论什么结果，仅剩下不到 3 种可能，可行！ |
| （A1、A2、A3）vs（A4、B1、B2） | 若 $A>B$，则剩下 5 种情况，排除 |
| （A1、A2、A3、A4）vs（B1、B2、C1、C2） | 不存在“小于”的可能性，排除 |
| （A1、A2、A3、B1）vs（A4、B2、C1、C2） | 若 $A>B$，则剩下 4 种情况，排除 |
现在我们找到了第一个可行的策略，即（A1、A2、B1）vs（A3、A4、B2）。以这一策略为基础，剩下的步骤不展开。
若选择 5 个球来比较，无外乎 6 种方法，其它方法都与其中一种等价或类似：
| 选取方式 | 分析 |
|---|---|
| （A1、A2、A3、A4）vs（B1、C1、C2、C3） | 不存在“小于”的可能性，排除 |
| （A1、A2、A3、B1）vs（A4、C1、C2、C3） | 不存在“大于”的可能性，排除 |
| （A1、A2、A3）vs（B1、B2、C1） | 不存在“小于”的可能性，排除 |
| （A1、A2、B1）vs（A3、B2、C1） | 无论什么结果，仅剩下不到三种可能，可行！ |
现在我们找到了另一个可行的策略，即（A1、A2、B1）vs（A3、B2、C1）。以这一策略为基础，剩下的步骤不展开。
解答已经完成。可以看到，即使已经具备解题思路，由于可能性比较复杂，要解释清楚整个策略依然不是一件轻松的任务。这个思路的关键在于测量作为一次信息编码的作用。理解这一点，才能够系统性地解答这个问题。
