双杯取水问题解析
引言
今天面试，面试官问了一道经典的问题：
一个5L的杯子和一个3L的杯子，水无限，如何得到4L水？
这个问题非常经典，经典到我下意识就能回忆起解法：
- 将5L杯子装满水，然后倒满3L的杯子，此时5L杯子里有2L水
- 将3L杯子清空
- 将5L被子里剩余的2L水导倒入3L杯子中
- 5L杯子取水，倒入3L杯，此时5L杯中就有4L水了
我们可以用表格来表达每一步的状态：
| 步骤 | 操作 | 3L杯内水的体积 | 5L杯内水的体积 |
|---|---|---|---|
| 1 | 5L杯取水 | 0L | 5L |
| 2 | 5L杯倒入3L杯 | 3L | 2L |
| 3 | 3L杯清空 | 0L | 2L |
| 4 | 5L杯倒入3L杯 | 2L | 0L |
| 5 | 5L杯取水 | 2L | 5L |
| 6 | 5L杯倒入3L杯 | 3L | 4L |
问题很简单，很好解决，接下来面试官问出了一个变种：杯子容量变成 7L 和 11L，取出 2L 水。
解法其实也不变，大杯接水倒小杯。接下来的表格中我们会用（容量）L 代表杯子，-> 代表水的流动：
| 步骤 | 操作 | 7L杯 | 11L杯 |
|---|---|---|---|
| 1 | -> 11L | 0L | 11L |
| 2 | 11L -> 7L | 7L | 4L |
| 3 | 7L -> | 0L | 4L |
| 4 | 11L -> 7L | 4L | 0L |
| 5 | -> 11L | 4L | 11L |
| 6 | 11L -> 7L | 7L | 9L |
| 7 | 7L -> | 0L | 9L |
| 8 | 11L -> 7L | 7L | 2L |
随后，面试官问出了终极难题：什么情况下这个问题无解？
证明
这个问题我在网上没有找到它的名字，我就将其命名为“双杯取水问题”好了。我们先只考虑我们目前的解法——即将大杯中的水倒入小杯，最后取得指定容量的水——这种情况下，会有那些情形是无解的。
我们假设大杯容量为M，小杯容量为N，每次我们能取出的特定容量为：
- M - N
- M - (N - (M - N)) = 2(M - N)
- M - (N - 2(M - N)) = 3(M - N)
- M - (N - 3(M - N)) = 4(M - N)
不难看出，每一步我们能取出的特定容量都为 n(M - N)，考虑每次我们还会将 N 的整数倍倒掉，最后的结果是 n(M-N) mod N。我的直觉告诉我，这个问题的解和 M - N 与 N 的最大公因数有关，如果最大公因数不为1，则会有无解的情况。要证明也不是很困难，我们画一个数轴就可以得到。假设最大公约数为a，M - N 为 b，则 nb 在数轴上一定会落到 a 的倍数上，而nN也一定会落到 a 的倍数上，所以 nb 减去 N 的整数倍后还是会落到 a 的整数倍上。在 a != 1 的情况下，a 的整数倍之间的空隙就是我们要找的无解的解。
换个角度
把 N 和 M 的整数倍都画在数轴上，也能很容易得出，用小杯往大杯倒水也是一样的效果，他们在数学上是等价的。这个问题的数学本质是在问 nN 与 mM 之间的差值。
当然，我们也很容易看出，当 M 和 N 都是整数的时候，我们是取不出小数升的水的。