[分享]倒腾问题

elimqiu

ysr

设M

elimqiu

应该只用这三个坛倒腾。所以一般地做 1+1+1+…+1 未必可能。

luyuanhong

[这个贴子最后由luyuanhong在 2011/02/06 10:00am 第 2 次编辑]

题  设正整数 m,n 互素（不妨设 m＜n）。取三个容量依次为 m,n,m+n 升的酒坛。
    起初，最大的坛装满了酒，另两个是空坛。证明：对任意 k∈{1,2,…,m+n} ，
    总可以通过若干次倒腾，让某个坛恰存有 k 升酒。

证  不妨把装 m 升的坛称为小坛，把装 n 升的坛称为中坛，装 m+n 升的坛称为大坛。
    因为 m,n 互素，所以，对任何正整数 k ，必有非负整数 a,b ，使得 an－bm＝k 。
    所以，当 k≤n 时，只要将大坛内的酒多次倒入中坛，重复倒满中坛 a 次，同时，
将中坛内的酒多次倒入小坛，重复倒满小坛 b 次，这样，中坛内剩余的酒就是 k 升。
    具体操作时，只有当中坛全部倒空时，才将大坛的酒倒入中坛。中坛的酒总是尽量
倒入小坛。小坛每倒满一次，就将小坛里的酒全部倒入大坛，成为空坛。
    例如，设 m＝4 ，n＝7 ，k＝2 。
    有非负整数 a＝2 ，b＝3 ，使得 an－bm＝2×7－3×4＝2＝k　。
    倒腾过程如下：
　 小坛　　　中坛　　　大坛
    0         0        11
    0         7         4   （第 1 次倒满中坛）
    4         3         4   （第 1 次倒满小坛）
    0         3         8
    3         0         8
    3         7         1   （第 2 次倒满中坛）
    4         6         1   （第 2 次倒满小坛）
    0         6         5
    4         2         5   （第 3 次倒满小坛）
    这样，重复倒满中坛 2 次，重复倒满小坛 3 次后，中坛剩余的酒就是 2 升。
    当 k＞n 时，必有非负整数 a,b ，使得 an－bm＝m+n-k 。
    用上面同样的方法，重复倒满中坛 a 次，重复倒满小坛 b 次，中坛剩余的酒
就是 m+n-k 升，再将小坛内的酒全部倒入大坛，大坛内的酒就是 k 升。

ysr

好，终于解决，谢谢教授的圆满解答

elimqiu

任何二正整数 a, b 的最大公因数可以表成 d = t·a - s·b, 其中 t, s 是正整数。这件事情在这个题目中很关键。
我们可以用辗转相除法等来证明这点。 有意思的是，还有一种非构造性的证明....

elimqiu

令 d 为 所有形如 t·a - s·b 的正数中的最小者： d = min { m | m = x·a - y·b > 0, x, y ∈ Z }
m 为 a , b 的最大公因数， 易见对某 s,t ∈ N+ 有 m |  t·a - s·b = d 于是 m ≤ d.
若 m < d, 则 d 不是 a,b 的公因数，不妨设 a = k·d + r, 0 < r < d, 那么就有
r = a - k·d = (1-kt)a-(-ks)b ∈ { m | m = x·a - y·b > 0, x, y ∈ Z },
这与 d 的最小性不合。 所以 d = m 是 a,b 的最大公因数。
d =  t·a - s·b = (t+kb)a - (s+ka)b, 当 k 充分大时 t+kb 及 s+ka 都是正数。
这就证明了楼上的论断：

下面引用由elimqiu在 2011/02/13 01:31am 发表的内容：
任何二正整数 a, b 的最大公因数可以表成 d = t·a - s·b, 其中 t, s 是正整数。