这个系列是MIT Open Courseware Mathematics for Computer Science^1的记录

倒水问题

---

有这么一个游戏：有两个桶a和b,容量分别是3 gal和5 gal,然后让你用这两个桶量出4 gal水来.如果用(a中剩余的水, b中剩余的水)来表示一个状态的话,整个过程表述如下:
$$(0, 0)\rightarrow(3, 0)\rightarrow(0, 3)\rightarrow(3, 3)\rightarrow(1, 5)\rightarrow(1, 0)\rightarrow(0, 1)\rightarrow(3, 1)\rightarrow(0, 4)$$

但是如果把a和b的容量换成3 gal和6 gal呢,还能量出刚好4 gal吗？直觉告诉我们不能.接下来为这个直觉寻找理论依据.

问题的形式化描述

---

对于上述的问题, 我们先对其进行形式化：

$给定两个桶a,b,桶a的容量为va,桶b的容量为vb. 且假定va \leq vb.$
$可以进行的操作有：清空一个桶,填满一个桶和将一个桶的水倒入另一个桶中.$
$以(x,y)记某个时刻的状态,表示a桶中有x \space gal水, b桶中有y \space gal水.$
$对与一个给定的数字r(0 \leq r \leq vb),能否达到某个状态(x’,y’), 使得r = x’ \lor r = y’?$

于是,整个过程是一个状态机,其起始状态为(0,0).可能的转换描述如下:

• $(x,y)\rightarrow(va,x).$
• $(x,y)\rightarrow(x,vb).$
• $(x,y)\rightarrow(0,y).$
• $(x,y)\rightarrow(x,0).$
• $(x,y)\rightarrow(x+y-vb,vb), if \space x+y \geq vb$
• $(x,y)\rightarrow(0,x+y), if \space x+y \leq vb$
• $(x,y)\rightarrow(va,x+y-va), if \space x+y \geq va$
• $(x,y)\rightarrow(x+y,0), if \space x+y \leq va$

问题的几个结论

---

$定理1: \forall k \forall(x,y)(k|va \land k|vb \rightarrow k|x \land k|y).$

可以很简单地用归纳法对以下invariant进行证明.

$P(n): (x,y)为n轮转换后的状态 \rightarrow k|x \land k|y.$

(0,0)时显然成立,下面证对于转换$(x,y)\rightarrow(x+y-vb,vb), if \space x+y \geq vb$成立,其余类似.

$let \space (x’,y’) \space be \space the \space next \space state$
$x’=x+y-vb, y’=vb$
$k|vb \implies k|y’$
$k|vb, k|x, k|y \implies k|x+y-vb \implies k|x’$
$P(n+1) \space holds$

定理1得证.
于是,对于$va=3,vb=6,r=4$的情况,由于对于任何$(x,y)$都有$3|x \land 3|y$,故不可能有$x=4 \lor y=4$的状态.
那么能否描述出可能达到的状态所满足的性质呢. 答案是肯定的. 首先可以确定的是所有状态$(x,y)$, 都满足x和y都是va,vb的线性组合,这是显然的. 其次,有如下事实.

$定理2: 所有va和vb的线性组合l1和l2(0 \leq l1, l2 \leq vb)所组成的状态(l1, l2)都是可到达的.$

首先,注意到对于任意的$l=p \times va + q \times vb(0 \leq l \leq vb)$, 无论p的正负, 都有办法写成$l=p’ \times va + q’ \times vb, p \gt 0$的形式.
理由如下：
对于$l=p \times va + q \times vb$,有$l=(p + m \times vb)\times va+(q-m \times va) \times vb$.
于是可以通过调整m的大小来将$p’=p + m \times vb$变为正数.
而对于$l=p’ \times va + q’ \times vb, p \gt 0$, 可以通过以下算法得到.

for i in [0, p') {
    fill a;
    while (a is not empty) {
        if b is full {
            empty b;
        }
        pour all the water in a into b;
    }
}

设最后的状态为$(x’, y’)$, 不难看出有$x’ = 0 \land y’ = p’ \times va + h \times vb$, 而由于限制条件$(0 \leq l \leq vb)$的存在. 可以得到$h=q’, 故y’ = l$. 目的达到. 定理二得证.

再回到定理1.
在众多满足条件的k中,gcd(va, vb)应该算是比较特殊的,而计算gcd(va, vb)的方法中,最常用的就是欧几里德算法.其证明也相对简单（只需证对于$a = p \times b + rem(a,b), 有gcd(a, b) = gcd(p, rem(a,b)$即可）.
那么问题来了, gcd(va, vb)是否是va, vb的一个线性组合呢？ 如果是的话. 由于所有va, vb在$(0, vb]$内的线性组合$l$都有$gcd(va,vb)|l$, 故gcd(va, vb)就有了一个新身份:
va, vb的最小正线性组合！
事实是不仅有, 而且还能很方便的算出线性组合系数,这个计算的方法,就是扩展欧几里德算法.

扩展欧几里德

---

首先还是来证明一下这一点:

$定理3:gcd(a,b)是a,b的一个线性组合.$

首先来证明:

$如果x, y都是a和b的线性组合, 那么rem(x, y)也是a和b的线性组合$

这很显然：

$令x=p1 \times a+q1 \times b, y=p2 \times a+q2 \times b$
$令x = k \times y + rem(x,y)$
$有rem(x,y) = x - k \times y \implies rem(x,y)=p1 \times a+q1 \times b -k \times p2 \times a - k \times q2 \times b$
$\implies rem(x,y)=(p1 - k \times p2) \times a + (q1 - k \times q2) \times b$
$\implies rem(x,y)为a和b的线性组合$

也就是说在欧几里德算法计算出的序列$(a, b)\rightarrow(b, rem(b,a))\rightarrow\cdots\rightarrow(x,y)\rightarrow\cdots\rightarrow(rem(t1, t2), 0)$中.
由归纳法可知，对于任意一个中间结果$(x, y)$，都有x和y是b的线性组合. 而最终的结果$rem(t1, t2) = gcd(a, b)$, 自然也是a和b的一个线性组合.
至于扩展欧几里德算法本身，已经包含在上面的证明中了。