小学奥数 -- 分油问题通解

学父五迁

题目：

三个桶。
10升桶，7升桶，3升桶。
10升桶里面装了10升油。
另外两个桶是空的。
没有其他量具，只能依靠倒满或倒空，把油。
不考虑油粘着桶壁剩余的问题。
请问，给定要求之后，分油的步骤如何？
比如，分成相同的两份，5升和5升。
比如，分成1升和9升。
比如，分成2升和8升。
比如，分成4升和6升。

学父五迁

又比如，

10升桶 -> 3升桶 -> 7升桶 -> 10升桶 -> 3升桶 -> 7升桶 -> ....

（产生数据的动作）     10升桶    3升桶    7升桶           
（初始）               10          0        0
（10升桶 -> 3升桶）    7           3        0
（3升桶 -> 7升桶）     7           0        3
（10升桶 -> 3升桶）    4           3        3              
（3升桶 -> 7升桶）     4           0        6
（10升桶 -> 3升桶）    1           3        6
（3升桶 -> 7升桶）     1           2        7
（7升桶 -> 10升桶）    8           2        0
（3升桶 -> 7升桶）     8           0        2
（10升桶 -> 3升桶）    5           3        2

学父五迁

定好一个循环方向，绝不回头，一步步倒下去，有限步骤后，就会分好。

比如，

10升桶 -> 7升桶 -> 3升桶 -> 10升桶 -> 7升桶 -> 3升桶 -> ....


（产生数据的动作）     10升桶    7升桶    3升桶           
（初始）               10          0        0
（10升桶 -> 7升桶）    3           7        0
（7升桶 -> 3升桶）     3           4        3              
（3升桶 -> 10升桶）    6           4        0              
（7升桶 -> 3升桶）     6           1        3
（3升桶 -> 10升桶）    9           1        0
（7升桶 -> 3升桶）     9           0        1
（10升桶 -> 7升桶）    2           7        1
（7升桶 -> 3升桶）     2           5        3

学父五迁

我把最简单最直接的思路先写出来。
这种思路不考虑整数拼凑，只是一个劲儿地按照一个循环方向倒油。

学父五迁

以上这两组特解，是否一定要用按照上述步骤，一步步求出来呢？
不一定，这个问题比较简单，也可以直接试出来。
我给出上述这些步骤，只是为了给出一个通用思路。
换成其他的度量桶（比如，5升桶和7升桶），也都适用。

学父五迁

以上这两组特解的绝对值最小，是两个最小步骤的解法（分别是两个不同的循环方向）。

学父五迁

现在，回到通解。

x = -10 + 7k
y = 5 - 3k

令 k = 2，那么，得到另一组特解。

x = 4
y = -1


这组特解意味着什么？

意味着，

从 10升桶 倒入 3 升桶 4 次，
从 7 升桶 倒入 3 升桶 1 次（7升桶倒满之后，要倒入10升桶） ，
就可以把油分出 5 升来。

学父五迁

这个特解的绝对值较大，不是最少步骤的解法。
先求出通解，再求最小绝对值的特解。

同样的道理，根据特解，得到通解如下。

x = -10 + 7k
y = 5 - 3k

令 k = 1, 那么，

x = -3
y = 2

这组特解意味着什么？

意味着，

从 10升桶 倒入 7 升桶 2 次，
从 3 升桶 倒入 10 升桶 2次，就可以把油分出 5 升来。

学父五迁

这个问题的特解，可以直接从 3x + 7y = 1 的一组特解得到。

3x + 7y = 1 的一组特解如下。

x = -2
y = 1

只要分别乘以5，就得到 3x + 7y = 5 的特解。

x = -10
y = 5

学父五迁

下面，再来看均分的情况，每份5升。

即，求解 二元一次 不定方程组 的整数解。

3x + 7y = 5

学父五迁

这两组特解，绝对值最小，
就是步骤最少的两种解法（分别是两个循环方向）。

学父五迁

现在，回到通解。

x = -2 + 7k
y = 1 - 3k

令 k = 1，那么，得到另一组特解。

x = 5
y = -2


这组特解意味着什么？

意味着，

从 10升桶 倒入 3 升桶 5 次，
从 3 升桶 倒入 7 升桶 2 次（7升桶倒满之后，要倒入10升桶） ，
就可以把油分出 1 升来。

学父五迁

有了这组特解，就可以得出通解。

x = -2 + 7k
y = 1 - 3k

为什么是这样的通解形式？
代入 3x + 7y = 1 试试就知道了。

3(-2 + 3k) + 7(1 - 3k) = 1  

这些都是数论中同余问题、剩余理论中的算法概念。

学父五迁

辗转相除法

7 / 3 = 2 + 1/3

7 - 2 X 3 = 1

得到一组特解。

x = -2
y = 1

这组特解意味着什么？

意味着，

从 10升桶 倒入 7 升桶 1 次，
从 7 升桶 倒入 3 升桶 2次，就可以把油分出 1 升来。

学父五迁

3x + 7y = 1

7 与 3 恰好互质，这个问题有 解。

（如果不互质，最大公约数大于1，就没有整数解。
比如，4x + 6y = 1 就没有整数解。
比如，4x + 6y = 2 就有整数解。
这些都是数论中同余问题、剩余理论中的算法概念。）

学父五迁

上述这些不定方程的解法，有通用的解法。
没有难度，但是，有复杂度。

解法很简单，就是用于求 最大公约数 的辗转相除法。

无论是分成怎样的两份。
都要从 母问题 开始。
母问题，就是 3x + 7y = 1

解出这个问题之后，其他的问题，都迎刃而解。

学父五迁

比如，分成相同的两份，5升和5升。

3x + 7y = 5

比如，分成1升和9升。

3x + 7y = 1

比如，分成2升和8升。

3x + 7y = 2

比如，分成4升和6升。

3x + 7y = 4

学父五迁

这个问题，可以转化为一个 二元一次 不定方程问题。

3x + 7y = 某一份油

求 x 和 y 的整数解。
x 和 y 可以为负数或正数。

如果为负数，表示 从本桶中 倒出 到 10升桶 几次。

如果为正数，表示 从另一个度量桶中 倒入 本桶 几次。

学父五迁

理解了这一点之后，剩下的问题就是3升桶和7升桶之间的关系了。
以下这个关系，比较难以理解。
由于水平所限，我也没有办法一言两语说清楚。
我直接给出解法描述。

学父五迁

首先，那个10升桶，实际上并没有在分油过程中起度量作用，只是一个临时过渡容器而已。
只要那个桶大于等于10升，对于问题本身都没有影响。
如果把10升桶换成11升桶、12升桶、100升桶，问题本质不会发生变化。
（当然，总油量不变，还是10升）