引子

有这么一道问题： 现有一瓶 10 ml 的水，和两个容量分别为 7 ml 和 3 ml 的空水瓶， 如何将 10 ml 的水平分成两个 5 ml ？

遇到一个问题，要看作一类问题，将这一类问题解决了，这一个问题就解决了， 以后遇到这样的每一个问题都解决了。

这个问题给出了具体的数值，我们可以替换为符号，然后用代数方法求解。 为了方便，将这类问题记为“三瓶水问题”。

数学模型

考虑一个二元组 $(c, w)$ 作为水瓶，其中 $c$ 是容量，$w$ 是水量。 有 3 个这样的瓶子，分别记为 $B_0=(c_0, w_0)$、$B_1=(c_1, w_1)$、$B_2=(c_2, w_2)$， 满足

倒水操作定义为关于 $w$ 的加减运算，例如从 $B_1$ 向 $B_2$ 倒水，先计算 $B_2$ 剩余容量， 如果大于等于 $B_1$ 水量，则 $B_2$ 水量加上 $B_1$ 水量，然后 $B_1$ 水量置零， 否则 $B_1$ 水量减去 $B_2$ 剩余容量，然后 $B_2$ 水量置满。

程序模拟

以上数学模型可以表示为以下程序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from dataclasses import dataclass

@dataclass
class Bottle:
    capacity: int
    water: int

    def __post_init__(self):
        # check the constraints
        pass

def pour(bottle1: Bottle, bottle2: Bottle) -> None:
    # pour from bottle1 to bottle2
    left_capacity = bottle2.capacity - bottle2.water
    if left_capacity >= bottle1.water:
        bottle2.water += bottle1.water
        bottle1.water = 0
    else:
        bottle1.water -= left_capacity
        bottle2.water = bottle2.capacity

数学归纳

从根本上解决问题还是需要数学方法，但是由于当前数学水平有限， 先从简单问题总结归纳得到猜想规律，以后有机会再做验证研究。

三瓶水问题可以拓展为分出 $[0,c_0]$ 之间任意整数的水量。 显然 $0,\ c_0,\ c_1,\ c_2$ 的水量一定可以得到，则 只需考虑 $[1,c_0-1]$ 之间的水量（不包含 $c_1,\ c_2$ ）。 另外易证，如果可以得到 $x$ 的水量，一定可以得到 $c_0-x$ 的水量，则 只需考虑 $[1,\lfloor c_0/2\rfloor]$ 之间的水量（不包含 $c_1,\ c_2$ ）。

简单例子

例 1

• $c_0=5,\ c_1=2,\ c_2=3$ ，考虑 $1$，显然可以得到。
• $c_0=5,\ c_1=1,\ c_2=4$ ，考虑 $2$，也可得到。

另外可以观察到，如果 $c_1$ 或者 $c_2$ 为 $1$，则所有水量一定可以得到。

例 2

• $c_0=6,\ c_1=2,\ c_2=4$ ，考虑 $1,\ 3$，无法得到。
• $c_0=6,\ c_1=3,\ c_2=3$ ，考虑 $1,\ 2$，无法得到。

例 3

• $c_0=7,\ c_1=2,\ c_2=5$ ，考虑 $1,\ 3$，可以得到。
• $c_0=7,\ c_1=3,\ c_2=4$ ，考虑 $1,\ 2$，可以得到。

思考与猜想

所有能得到的数都是通过 $c_0,\ c_1,\ c_2$ 以及它们的和差之间的加减运算得到的。

1. $c_0$ 只能作为被减数，用于计算某一水量 $x$ 的补水量，即 $c_0-x$。
2. $c_1$ 和 $c_2$ 只能用大数 $c_1$ 减去小数 $c_2$ 得到 $x$ 。
3. 如果 $x$ 是一个新值，则可以与 $c_2$ 做减法，尝试与 $c_1$ 做加法，否则结束。

新值即属于考虑集合但之前还未得到的值。

大胆的猜测：考虑集合内属于 $c_0,\ c_1,\ c_2$ 最大公约数的值一定可以得到。 方法可能比较复杂，但一定存在，整体思路如上 3 个步骤。

该猜测在简单问题上已验证，但还未得到严格的数学证明。

附：解决引子问题

首先定义水瓶 $B_0=(10, 10),\ B_1=(7, 0),\ B_2=(3, 0)$， 然后倒水，以下左边是方向，右边是完成状态：