趣题:只允许加倍操作的水桶倒水问题

    今天的题目来自这里。有三个水桶,它们里面分别装了 a 升的水、 b 升的水和 c 升的水(其中 a 、 b 、 c 都是正整数,桶本身没有容量限制)。你可以把水从一个桶倒进另一个桶,但必须保证让后者的水量刚好变成原来的两倍。证明,不管 a 、 b 、 c 是多少,你总能让其中某一个水桶变空。

    例如,假设初始时 (a, b, c) = (3, 2, 1) ,那么你可以先把 (3, 2, 1) 变成 (1, 4, 1) ,再把它变成 (2, 4, 0) ,从而把第三个水桶变空。


    让我们先来看一个特殊的情形。假如只有两个水桶,并且其中一个水桶的水量为奇数,另一个水桶的水量为偶数。由于我们只有两个水桶,并且它们的水量也不相等,因此我们只有唯一一种可行的操作:拿起水多的桶,把水倒进水少的桶。注意,每次操作之后,两个桶里的水量仍然是一奇一偶,因此我们还能继续操作下去,永远不会“走死”。

    但是,两个桶里的水量只有有限种组合,因而如果我们一直这么走下去,最终必然会和原来的某个状态重合,从而产生循环。事实上,第一个重复的状态一定就是初始时的状态,而不会是半路中的某个状态;换句话说这个循环一定是一个完整的圈,而不是一个 ρ 字形的循环。这是因为,每一个状态都只能由唯一的“前继状态”变过来,即水量为偶数的那个桶其中一半的水在另一个桶中。

    这意味着,如果循环的长度是 n ,那么经过 n – 1 步移动之后,我们就能到达初始状态的前继。换句话说,假如 a 是一个偶数, b 是一个奇数,那么我们就有了一种把 (a, b) 变成 (a/2, b + a/2) 的方法。

 
    让我们来看看一些更复杂的情况。假如初始时三个桶的水量分别是奇、偶、偶,下面我们给出一种方法,它能增加“奇数桶”里的水量,同时保持另外两个桶里的水量仍是偶数。把三个桶里的水量分别记作 (a, b, c) ,其中 a 是奇数, b 和 c 都是偶数。如果 b 和 c 都不能被 4 整除的话,可以在它们俩之间倒一次水,让其中一个桶里的水量变成 4 的倍数(同时另一桶水的水量仍是偶数)。现在,无妨假设 b 的水量是 4 的倍数。我们把 (a, b) 变成它的前继,从而让三个桶里的水量分别变成 (a + b/2, b/2, c) 。这样一来,三个桶里的水量仍是奇、偶、偶,但“奇数桶”里的水量变多了。

    不断重复上述操作,让“奇数桶”里的水越来越多,同时保持另外两个桶的水量始终是偶数。最终,总有一个“偶数桶”会变空。因此,我们就解决了三个桶分别为奇、偶、偶的情况。

 
    其他情况呢?随便走一步,奇、奇、奇的情况立马就变成了奇、偶、偶,因此奇、奇、奇的情况也就解决了。现在,我们只剩下奇、奇、偶和偶、偶、偶的情况。在两个“奇数桶”之间倒水,可以把奇、奇、偶变成偶、偶、偶。而初始情况为偶、偶、偶,这意味着以后三个桶里的水量也永远都是偶数,因此我们可以把所有桶里的水量都除以 2 ,从而化为规模更小的情况。我们可以用这种方法不断减小问题的规模,直到把问题化为我们已解决的状态为止。至此,这个问题便彻底解决了。

 
    这是一个非常经典的题目了,它也出现在了趣题王 Peter Winkler 的 Mathematical Puzzles 一书中。在书里, Peter Winkler 指出,这道题出自第五届全苏数学奥林匹克竞赛中,随后又出现在了 1993 年的 Putnam 竞赛中。 Peter Winkler 还在书里提到了另一个答案,这是由 Svante Janson 首先给出的。

 
    为了解释清楚,还是让我用一个例子来说明吧。不妨假设这三个桶里的水量分别为 67 升、 10000 升和 12345 升。把三个桶按照水量从少到多排列,依次编号为 A 、 B 、 C 。下面我们给出一个过程,它能把 B 里的水变得比 A 更少。先计算 10000 除以 67 ,结果等于 149 余 17 。把 149 转换为二进制 10010101 。现在,从这个二进制数的最低位开始,从右往左依次查看各个数字:每读到一个 1 ,就把 B 倒进 A ;每读到一个 0 ,就把 C 倒进 A 。容易看出,最后 A 中的水量变成了原来的 28 = 256 倍,其中 B 贡献了 149 倍。因此, B 总共倒出了 149 × 67 升的水,因而 B 里面将会只剩下 17 升的水。由于 17 这个数字是 10000 除以 67 的余数,因此它是一个比 67 小的数。这意味着,我们有了一种刷新水量最小值的方法。不断执行这个过程,最终总能把其中一个桶里的水量变为 0 。

    且慢,我们还需要证明,为了完成上述过程, C 里面储备有足够多的水。这很容易看出来,因为在最坏情况下,二进制数恰好为 1000..00 ,但即使是这样, C 需要贡献的水量也不会比 B 更多。然而, C 本来拥有的水量是三个桶里最多的,因此我们永远不用担心 C 里的水不够。

22 条评论

发表评论