Puzzle Toad-5 Empty the bucket

Puzzle Toad-5 Empty the bucket #

题目翻译 #

你现在身处沙漠, 并且拥有 $3$ 个桶 (桶的容量无限) , 里面分别有 $a, b, c$ 盎司的水. 这里 $a, b, c$ 都是正整数. 出于某个原因, 你现在需要一个空桶. 因为在沙漠中你非常需要水, 所以不能简单地把水倒掉来得到一个空桶. 你不得不把水从一个桶倒到另一个桶中. 不过在每次倒水时, 你必须让接收水的水桶中的水数量变为原来的两倍 (也就是说, $a\rightarrow b$ 会使得 $a, b$ 变为 $a - b, 2b$). 举例来说, 水桶中的水变化的情况可能是这样的: $$ 3\quad 2\quad 1\ 1\quad 4\quad 1\ 0\quad 4\quad 2\ $$ 证明: 无论初始的水量是多少, 在这种约束下你总是可以得到一个空桶.

解答 #

解法 1 #

两个水桶的特殊情况 #

首先考虑只有一奇一偶两个水桶, 看看对它们进行操作会发生什么. 因为只有两个不相等的水桶, 只有一种可能的行动: 把水多的水桶向水少的水桶中倒水. 注意到这个操作使得两个水桶仍然是一奇一偶. 如果一直重复这个操作, 会发生什么? 既然水桶状态的总数有限, 最终一定会回到某个之前出现过的状态上. 事实上, 第一个重复的状态就是初始的状态. 这是因为对于序列中的任何一种状态, 它的前一个状态都是唯一的, 把偶数桶的一半水放到奇数桶中, 就能得到这个状态. 如果状态构成的环大小是 $n$ , 那么通过 $n - 1$ 次移动, 就能从初始状态到达初始状态的 “前一个” 状态. 也就是说, 如果初始状态是 $(a, b)$ , $a$ 是偶数而 $b$ 是奇数, 那么我们可以让水桶变为 $(\frac{a}{2}, b + \frac{a}{2})$ .

“奇偶偶” 的解法 #

对此有把握后, 考虑一个稍微一般点的情况. 假设现在有 $3$ 个水桶, 第一个为奇数, 剩余两个为偶数, 称为 “奇偶偶” 的情况. 事实上, 我们可以在不断增加奇数桶水量的同时保持另外两个桶仍然是偶数桶, 按照这一结论, 最终一定会有某一时刻, 一个偶数桶变成了空桶. 下面来说明具体的操作: 假设水量分别为 $a, b, c$ , $a$ 为奇数, $b, c$ 为偶数. 首先, 如果 $b, c$ 都不是 $4$ 的倍数, 可以在 $b, c$ 之间倒一次水, 这样就能得到一个 $4$ 的倍数, 同时另一个仍然是偶数. 因此, 可以直接假设 $b$ 为 $4$ 的倍数, $c$ 为偶数. 这时, 我们应用两个水桶时的结论, 把 $(a, b)$ “回溯” 到前一个状态, 得到 $(a + \frac{b}{2}, \frac{b}{2})$ , 因为 $b$ 为 $4$ 的倍数, 所以现在 $a + \frac{b}{2}, \frac{b}{2}, c$ 仍然是 “奇偶偶” 的模式. 重复这一模式 (用偶数桶构造出 $4$ 的倍数, 再向奇数桶倒水) , 最终一定会有一个偶数桶变为空桶. 这样我们就解决了 “奇偶偶” 的情况.

其它情况等价于 “奇偶偶” #

对于剩下的情况呢? “奇奇奇” 的情况很简单, 随便倒一次水就化归成了 “奇偶偶” 的情况. 对于 “偶偶偶” 的情况, 把每个桶的水量都除以 $2$ 的问题与原问题是等价的. 而对于 “奇奇偶” 的问题, 在两个奇数桶之间倒一次水, 就变为了 “偶偶偶” 的情况, 可以进一步减小问题规模. 因此, 最终 “偶偶偶” 和 “奇奇偶” 都能化为 “奇偶偶” 的情况.

解法 2 #

把 $3$ 个水桶按水量从小到大排列, 记作 $A, B, C$ . 下面给出一种操作, 使得 $B$ 中的水会变得比 $A$ 中的水少. 作带余除法 $B ÷ A = x\times A + y, 0\leq y< A$ . 把 $x$ 写成二进制形式, 然后从低位向高位遍历, 遇到 $1$ 就从 $B$ 向 $A$ 倒水, 遇到 $0$ 就从 $C$ 向 $A$ 倒水. 容易证明这个过程就是在模拟带余除法, 最终 $B$ 剩下的水量恰好就是 $y < A$ . 这个过程是肯定能实现的, 因为排序保证了 $A\leq B\leq C$ , 而过程中 $B$ 至多倒 $x\times A\leq B$ 分量的水, $C$ 至多倒 $x\times A - 1 < C$ 分量的水. 不断重复这个操作, 我们就能不断刷新 $3$ 个水桶中水量的最小值, 最终会得到一个空桶.

补充 #

这道题和它的两种解法, 出自 Peter Winkler 的文章 Five Algorithmic Puzzles .