龙胆虎威 3 中的一个场景:在泉水旁有两个瓶子,容量分别是 5 加仑和 3 加仑。 Bruce 需要在 5 分钟内精确地得到 4 加仑水来停止定时器,差一盎司都会引起爆炸。可是用这两个瓶子总是能构造出来要求的水量吗?如果能,那么有确定的数学方法来告诉 Bruce 具体的步骤吗?

本文对这个问题进行推广,分别讨论有解的条件解的构造两个问题,再给出判断是否有解的简单方法。有关解的存在性,我们主要证明以下两个命题:

如果目标水量 c 能够写成 a 和 b 的线性组合就有解,否则无解。具体地:

  1. 得到的水量一定是 a 和 b 的线性组合。即如果 c 不是 a 和 b 的线性组合就无解。
  2. 重复地把 a 接满倒入 b,b 满了就倒掉,a 空了就装满,就可以得到在 b(假设 b > a)中得到所有线性组合。即只要能写作线性组合就一定会得到。

c 是否能写作 a 和 b 的线性组合,取决于 c 能否被 gcd(a,b) 整除:

  1. gcd(a,b) 是 a 和 b 最小的正的线性组合。
  2. gcd(a,b) 能整除 c 等价于 c 是 a 和 b 的线性组合。

为方便讨论,本文所有线性组合都指整数线性组合,所有数字 x、y、m、n 都表示整数。

剩余水量总是 a 和 b 的线性组合

设 a 中的水为 $V_a$,b 中的水为 $V_b$,用数学归纳法可以很容易证明 $V_a$ 和 $V_b$ 总是 a 和 b 的线性组合

一、初始态两个瓶子都是空的,$V_a=V_b=0$ 是 a 和 b 的线性组合。

二、后续我们有三种操作:

  1. 把其中一个倒掉。这个瓶子的水量变成 $V_a=0 \ \textrm{or} \ V_b=0$,是 a 和 b 的线性组合;另一个瓶子的水量不变。
  2. 把其中一个灌满水。这个瓶子水量变成 $V_a=a \ \textrm{or} \ V_b=b$,是 a 和 b 的线性组合;另一个瓶子的水量不变。
  3. 把 a 倒入 b,直到 b 满了或者 a 空了。
    • 如果 b 满了:$V'_b=b$,是 a 和 b 的线性组合;设操作前 $V_a=ra+sb, V_b=ma+nb$ 则从 a 倒出的水量 $-\Delta V_a=\Delta V_b=(1-n)b-ma$,那么 A 剩余的水量 $V'_a=(r+m)a+(s+n-1)b$,是 a 和 b 的线性组合。
    • 如果 a 空了:$V'_a=0$ 是 a 和 b 的线性组合;设操作前 $V_b=ma+nb$,则操作后 $V'_b=(m+1)a+nb$ 仍然是 a 和 b 的线性组合。

结论:$V_a$ 和 $V_b$ 总是 a 和 b 的线性组合。

所有 a 和 b 的线性组合都可以得到

我们给一个神奇的操作:不断地把 a 装满,倒入 b 中。如果 b 满了就都倒掉,a 倒空后再装满。它可以得到所有的线性组合。 下面来证明这一点,既然 c 是 a 和 b 的线性组合,它就可以表示为:

\[c=ma+nb, \quad b \geq a, \quad c > 0\]

其中:

  • $b \geq a$:假设 $b$ 是大的那个瓶子,即我们总把大的那个放在右手边,最后我们会在 $b$ 中得到量为 $c$ 的水。
  • $c>0$:假设我们要的水量 $c$ 是大于 $0$ 的,不然直接给空瓶子就行。

虽然我们不知道 $m$ 和 $n$ 的确切值,但我们知道存在这样的 $m$ 和 $n$。 同时,我们还可以把 $m$ 调整为正数:如果 $m$ 不是正数,就把它增加 $b$,同时 $n$ 减小 $a$ 使得上式仍然成立。 现在我们有:

\[c=ma+nb, \quad b \geq a, \quad m>0, \quad c > 0\]

这时 $m > 0$,而 b 中要能装得下 c,所以 $ma+nb \leq b,n \leq 1-m\frac{a}{b} < 1$,即 $n \leq 0,\quad \mid n \mid = -n$。

\[c=\mid m \mid a- \mid n \mid b, \quad b \leq a, \quad m > 0, \quad c > 0\]

我们在重复这一神奇操作 $\mid m \mid$ 次时,共有 $\mid m \mid a$ 的水倒入了 b。而 b 也恰好被倒掉过 $\mid n \mid$ 次:

  • 如果被倒掉过 $ \mid n \mid +1$ 次,则 b 中剩余 $ \mid m \mid a- \mid n \mid b-b=c-b<0$,不可能倒成负数。
  • 如果被倒掉过 $ \mid n \mid -1$ 次,则 b 中剩余 $ \mid m \mid a- \mid n \mid b+b=c+b>b$,b 中装不下。

这样在我们重复 $ \mid m \mid $ 次操作时,就得在 b 中得到了 $ \mid m \mid a- \mid n \mid b = c$ 的水。 注意我们并没有指定 c 是多少,也就是说对于任意 c,都可以通过若干次操作得到。 这就是神奇操作神奇的地方:我们不需要事先算好 $m$ 的值,只要不断地重复操作,b 中的水量为 c 时停止就好。

因此,只要 c 是 a 和 b 的线性组合(当然必须装得下)就可以得到。 对于龙胆虎威中 $a=3,\ b=5,\ c=4$ 的例子,$gcd(3,5)=1$,因此可以得到所有可能的水(1,2,3,4,5)。得到 $V_{b}=4$ 的操作顺序是:

第一次操作:

$V_{a}=3, V_{b}=0 \quad \rightarrow \quad V_{a}=0, V_{b}=3$

第二次操作:

$V_{b}=3, V_{b}=3 \quad \rightarrow \quad V_{a}=1, V_{b}=5 \quad \rightarrow \quad V_{a}=1, V_{b}=0 \quad \rightarrow \quad V_{a}=0, V_{b}=1$

第三次操作:

$V_{a}=3, V_{b}=1 \quad \rightarrow \quad V_{a}=0, V_{b}=4$

gcd(a,b) 是 a 和 b 最小的正的线性组合

我们先证明一个猜想: gcd(a,b) 是 a 和 b 最小的正的线性组合。 即假设 $c=ma+nb$ 是 a 和 b 的最小正数组合,则 $c=gcd(a,b)$。证明思路是先证明 $c\leq gcd(a,b)$,再证明 $c \geq gcd(a,b)$。

1. $gcd(a,b) \leq c$

设 $G=gcd(a,b),\ a=xG,\ b=yG$,则 $c=ma+nb=(mx+ny)G$。由于 $c>0$,所以 $mx+ny \geq 1,c=(mn+ny)G \geq G$。得证。

MIT 教材中有另一种证明:因为 $gcd(a,b) \mid a$,且 $gcd(a,b) \mid b$,所以 $gcd(a,b) \mid ma+nb, \ for \ \forall m, n$。c 是 $ma+nb$ 的特例因此 $gcd(a,b) \mid c$,这意味着 $gcd(a,b) \leq c$。

2. $gcd(a,b) \geq c$

由于 gcd(a,b) 是最大公约数,我们通过证明 c 也是 a 和 b 的公约数,来证明 $gcd(a,b) \geq c$。 为此只需要证明 $c \mid a$,根据对称性可以得到 $c \mid b$。设 a 除以 c 的商是 x,余数是 $0 \leq y \lt c$,则:

\[a=xc+y=x(ma+nb)+y\]

得到 $y=(1-mx)a-nxb$,即 y 也是 a 和 b 的线性组合。由于 c 是最小的正的线性组合,所以 $y \geq c$ 或 $y \leq 0$。 由于 $y$ 是余数 $0 \leq y \lt c$,取交集 $y=0$。即 a 可以被 c 整除。得证。

gcd(a,b) 能整除 c 等价于 c 是 a 和 b 的线性组合

这里我们要证明 a 和 b 的线性组合的集合,就是 gcd(a,b) 的倍数构成的集合。为此我们需要证明两个事情:

  1. a 和 b 的线性组合都是 gcd(a,b) 的倍数
  2. gcd(a,b) 的倍数是 a 和 b 的线性组合

对于1,由于 $gcd(a,b) \mid a,gcd(a,b) \mid b$,因此 $gcd(a,b) \mid xa+yb$,1 得证。

对于2,上一节证明了 $gcd(a,b)$ 是 a 和 b 最小的正的线性组合。 $gcd(a,b)$ 的倍数自然也是 a 和 b 的线性组合,2 得证。

推论:目标 c 能够被 gcd(a,b) 整除就有解,否则无解。上面几节我们证明了是否是线性组合决定了是否有解,而是否是线性组合取决于是否是 $gcd(a,b)$ 的倍数,因此:

\[c 是否能够得到(有解) \quad \equiv \quad \exists m, n: c=ma+nb \quad \equiv \quad c \mid gcd(a,b)\]

本文采用 知识共享署名 4.0 国际许可协议(CC-BY 4.0)进行许可,转载注明来源即可: https://harttle.land/2019/09/21/die-hard-problem.html。如有疏漏、谬误、侵权请通过评论或 邮件 指出。