韩信分油问题:只借助两个容量分别为7升和3升的不规则且无刻度的容器,如何让两人平分一桶10升的油?
解:用有序对/a,b/表示大容器的油量为a升,小容器的油量为b升。初始状态为/0, 0/,即两个容器都是空的。再用X、A、B分别代表油桶、大容器和小容器。并用变换MtoN表示从M往N中倒油(当N为X时即为倒空M;当N不为X时为倒满N或倒空M,且二者必居其一)。于是一个可行的分油过程如下:
/0, 0/ XtoA /7, 0/ AtoB /4, 3/ BtoX /4, 0/ AtoB /1, 3/ BtoX /1, 0/ AtoB /0, 1/ XtoA /7, 1/ AtoB /5, 3/ BtoX /5, 0/
最后大容器里以及油桶里的油量各占5升,达到了平分的目的。
来看一下大容器在上述过程中油量的变化情况:0,7,4,1,0,7,5
对应的等式分别为:7·0 = 0,7·1 = 7,7·1 - 3·1 = 4,7·1 - 3·2 = 1,7·0 = 0,7·1 = 7,7·1 - [3·1 - (7·1 - 3·2)] = 5
接下来,容易想到如下一个扩展的问题:
从一个无穷大的油桶里取油,只借助两个容量分别为7升和3升的不规则且无刻度的容器,所能表示的整数升油量有哪些?
解:由之前的题解,已经知道这两个容器可以表示的整数升油量可以为0、1、3、4、5、7、8。
10是显然可以的,对应把A和B都注满的情形。
由以下变换可知2、6、9也都可以表示出来:
/5, 0/ AtoB /2, 3/
/0, 3/ BtoA /3, 0/ XtoB /3, 3/
/2, 3/ BtoX /2, 0/ AtoB /0, 2/ XtoA /7, 2/
因此,此题的解为0到10的全体整数。
换两个数,再考察一下,比如:
从一个无穷大的油桶里取油,只借助两个容量分别为7升和5升的不规则且无刻度的容器,所能表示的整数升油量有哪些?
解:最小值0和最大值12是显然可以的。5和7,以及它们的差,即2,也是显然可以的。9(2+7)和10(5+5)也可以。
由以下变换过程:
/7, 2/ AtoB /4, 5/ BtoX /4, 0/ AtoB /0, 4/ XtoA /7, 4/ AtoB /6, 5/ BtoX /6, 0/ AtoB /1, 5/ BtoX /1, 0/ AtoB /0, 1/ XtoA /7, 1/ AtoB /3, 5/
可知,4、11、6、1、8、3也都是可以表示的。
综上,此题的解为0到12的全体整数。
由以上的分析,推测会有以下一般性的结论:
从一个无穷大的油桶里取油,只借助两个不规则且无刻度的容器,容量分别为a升和b升,a和b均为正整数,且满足(a, b) = 1。则所能取得的整数升油量为0到a+b范围内的全体整数。
证明:a = b的情形只可能是 a = b = 1,命题显然成立。以下考虑 a ≠ b 的情形,由结论的对称性,不妨假设 a > b。
a升的容器记为A,b升的容器记为B,油桶记为X。先把容器A和B注满,即XtoA, XtoB,得到a+b升油量;再把容器B倒空,并用容器A中的油注满容器B,即BtoX, AtoB,得到a升油量;此时若A中油量不为0,则继续重复做BtoX, AtoB操作。这一连串的过程可以得到:
a+b ≡ a ≡ a-b ≡ ... ≡ r1 (mod b) ①
其中 r1 满足 a+b = q1·b + r1, q1 > 0, 0 ≤ r1 < b
当 b = 1 时,r1 = 0,由①知命题显然成立。
当 b > 1时,由(a, b) = 1,可知 0 < r1 < b。上面的操作最后得到的状态是 /0, r1/,再次注满容器A,并用A中的油注满B,即XtoA, AtoB,此时的状态为 /a+r1-b, b/;接着再次重复上面的BtoX, AtoB操作,直到容器A中的油量为空为止。这一连串的过程可以得到:
a+r1 ≡ a+r1-b ≡ ... ≡ r2 (mod b) ②
其中 r2 满足 a+r1 = q2·b + r2, q2 > 0, 0 ≤ r2 < b, r2 ≠ r1
这里对 r2 ≠ r1 说明一下,假如r1 = r2,则由①和②便有 a+b ≡ a+r1 (mod b),这与 0 < r1 < b 矛盾。
当 b = 2 时,由①知,r1 = 1,再结合②可知,r2 = 0,则①和②分别涵盖了0到a+2的所有奇数和偶数,命题成立。
当 b > 2 时,必有 r2 ≠ 0,否则 a+r1 ≡ a+(a+b) ≡ 0 (mod b),即有 b | 2a,再由 (a, b) = 1,知 b | 2,这与 b > 2 矛盾。继续上面的操作,会得到:
a+r2 ≡ a+r2-b ≡ ... ≡ r3 (mod b) ③
其中 r3 满足 a+r2 = q3·b + r3, q3 > 0, 0 ≤ r3 < b, r3 ≠ r2, r3 ≠ r1
这里对 r3 ≠ r2 说明一下,假如r3 = r2,则 a+r2 ≡ a+r1 (mod b), 这与 r2 ≠ r1 矛盾。
当 b = 3 时,由①和②知,r1和r2必然是一个为1、一个为2,于是r3 = 0,则①、②和③一起涵盖了0到a+3的全体整数,命题成立。
按照上面的操作,当 b = k (k > 3)时,会有以下 k 个同余关系:
a+k ≡ a ≡ a-k ≡ ... ≡ r1 (mod k)
a+r1 ≡ a+r1-k ≡ ... ≡ r2 (mod k)
a+r2 ≡ a+r2-k ≡ ... ≡ r3 (mod k)
...
a+rk-1 ≡ a+rk-1-k ≡ ... ≡ rk (mod k)
其中 r1 满足 a+k = q1·k + r1, q1 > 0, 0 ≤ r1 < k;ri 满足 a+ri-1 = qi·k + ri, qi > 0, 0 ≤ ri < k, (i = 2, 3, ..., k)。
下面来证明 r1, r2, ..., rk-1 都不能等于0:
假如 r1 = 0,则由 a+k ≡ a ≡ 0 (mod k),知 k | a,而 k > 3,这与(a, k) = 1矛盾,故 r1 ≠ 0;
假如 r2 = 0,则由 a+r1 ≡ a+a ≡ 0 (mod k),知 k | 2a,再由 (a, k) = 1,有 k | 2,这与 k > 3 矛盾,故 r2 ≠ 0;
假如 r3 = 0,则由 a+r2 ≡ a+(a+r1) ≡ a+a+a ≡ 0 (mod k),知 k | 3a,再由 (a, k) = 1,有 k | 3,这与 k > 3 矛盾,故 r3 ≠ 0;
...
假如 rk-1 = 0,则由 a+rk-2 ≡ a+(a+rk-3) ≡ ... ≡ (k-1)·a ≡ 0 (mod k),知 k | (k-1)·a,再由 (a, k) = 1,有 k | k-1,这与 k > k-1 矛盾,故 rk-1 ≠ 0。
接着证明 r1, r2, ..., rk-1, rk 两两互不相等:
假如 r2 = r1,则由同余关系有 a ≡ a+r1 (mod k),这与 0 < r1 < k 矛盾,故 r2 ≠ r1;同样,可知 r3, ..., rk-1, rk 也都不等于 r1;
假如 r3 = r2,则由同余关系有 a+r2 ≡ a+r1 (mod k),这与 r2 ≠ r1 且 0 < r1 < k, 0 < r2 < k 矛盾,故 r3 ≠ r2;同样,可知 r4, ..., rk-1, rk 也都不等于 r2;
...
假如 rk-1 = rk-2,则由同余关系有 a+rk-2 ≡ a+rk-3 (mod k),这与 rk-2 ≠ rk-3 且 0 < rk-3 < k, 0 < rk-2 < k 矛盾,故 rk-1 ≠ rk-2;同样,可知 rk 也不等于 rk-2;
假如 rk = rk-1,则由同余关系有 a+rk-1 ≡ a+rk-2 (mod k),这与 rk-1 ≠ rk-2 且 0 < rk-2 < k, 0 < rk-1 < k 矛盾,故 rk ≠ rk-1。
综上, r1, r2, ..., rk-1, rk 这 k 个整数两两不等,且 r1, r2, ..., rk-1 全都大于0且小于k,再由 0 ≤ rk < k,知 rk = 0(否则 rk 必然要和前面 k-1 个数之一相等)。
由以上分析,上面的 k 个同余关系就涵盖了 0 到 a+k 范围内的全体整数,因此对任意 b = k, k > 3 的情形命题成立。
综上,命题得证。
由两个容器还可以拓展到更一般的情形:
用 n (n > 1) 个不规则无刻度的容器从一个无穷大的油桶里取油,这些容器容量都为整数升,分别记为 a1, a2, ..., an ,且满足(a1, a2, ..., an) = 1。则所能取得的整数升油量为0到s范围内的全体整数,s = a1+a2+...+an。
n = 2 的情形就是上述刚才已经证明过的那个命题。当 n > 2 时,要用到如下一个引理,利用这个引理,n > 2 的情形可以等价为 n = 2 的情形。
引理 若n个正整数满足 (a1, a2, ..., an) = 1,并记 s为这n个数的和,则有 min{ (a1, s), (a2, s), ..., (an, s) } = 1。
比如,n = 3,3个容器的容量分别为3升、5升和7升,s = 3+5+7 = 15,(3,15) = 3, (5, 15) = 5, (7, 15) = 1,即有 (a3,s) = 1,即 (a3,s-a3) = 1
s-a3 = a1+a2,这时,把容量为a1和容量为a2的容器看成一个容器,其容量为 a1+a2=3+5=8,用这个复合容器和容量为a3=7的容器按前述的方法取油,所能取得的整数升油量必然为0到s范围内的全体整数。
遗憾的是,这个引理,我还没有找到方法证明。
联系客服