倒水问题

发表于   |   分类于   |   本文阅读量

对酒当歌，人生几何。 大浪淘尽，数论风流。 ——转自网络

若无特殊说明，本文均在整数范围内进行讨论。

00 序

小学数学中，这类问题很常见：有无穷多的水，有一个容量为 \(a\) 升的桶和 \(b\) 升的桶，如何量出 \(c\) 升的水？

A.Coble是上个世纪美国的院士，做代数几何，一度很有影响。据称，他有无穷多个博士论文的题目：当你证明了一个2维的情况的时候，他叫下一个博士生去证明3维的情况，然后叫下下个博士生去做4维的。后来有个叫Gerald Huff的博士，不但做了5维的情况，而且对一般的n也解决了。这就让Coble的未来的无穷个博士无所事事了。Coble很怒。 转自 https://www.guokr.com/question/483928/

简单难度：3L桶和5L桶，倒出1L水。可以容易想到，首先3L桶装满倒入5L桶，然后3L桶装满，再将3L桶中的水倒入5L桶使其装满，此时3L桶刚好剩下1L水。

难度高一点：13L桶和7L桶，倒出4L水。该怎么解？

进一步，对于任意 \(a\) 升桶和 \(b\) 升桶，我们能否倒出 \(c\) 升水，若能，该怎么倒？

事实上，不论是从数学角度还是从计算机角度，都已有相关讨论。本文其实没太大意义。

01 问题描述

有无穷多的水，有一个容量为 \(a\) 升的桶和 \(b\) 升的桶，现在要确定能否倒出 \(c\) 升水，如果能，找出方案。为方便叙述，将容量为 \(a\) 升、\(b\) 升的桶记为 \(a\) 桶、\(b\) 桶。

在这个问题中，我们有3个基本操作：

  1. 将桶装满水
  2. 将桶中水全部倒出
  3. 将一个桶中的水倒入另一个桶，此时有2个可能：a)全部倒入另一个桶中，自身清空。b)将另一个桶装满，自身还有水。

02 分析

首先给出结论，这个问题有解当且仅当关于 \(x,y\) 的方程 \(xa + yb = c\) 有解，下面给出证明。

充分性：当 \(xa + yb = c\) 有解时，我们可以根据该方程量出 \(c\) 升水，具体步骤在下文给出。

必要性：当能倒出 \(c\) 升水时，由基本操作可知，增加或减少的水量都是 \(a\) 升或 \(b\) 升，因此最后的结果必然是 \(c = xa + yb\) 的形式。

此外，\(xa + yb = c\) 有解也等价于 \(\gcd(a,b) | c\)。

对于 \(a,b\)，不妨设 \(a,b\) 互素即 \(\gcd(a,b) = 1\)，并且 \(a > b\)。因为如果不互素，我们在所有的这些操作中，将桶的容量、倒入倒出的水都除以 \(\gcd(a,b)\)，除以 \(\gcd(a,b)\) 之后两桶的容量便是互素的，并且结果仍然一致。此外如果 \(a < b\)，将两个桶互换即可。

对于 \(c\)，显然 \(c\) 应该在\([1, a)\) 范围内，这个范围之外的 \(c\) 是没有意义的。并且我们只需处理 \(c \in [1, b)\) 的情况，这是因为得到了 \([1, b]\) 内的水，对于 \(c > b\)，只需要在 \(a\) 桶中量出 \(c \mod b\) 升水，再往 \(a\) 桶中加 \(\dfrac{c}{b}\) 次装满的 \(b\) 桶的水即可。

当我们确定了 \(x,y\) 满足 \(xa + yb = c\)，可以知道 \(x,y\)。于是我们调整符号，使 \(xa - yb = c\)，此时 \(x,a,y,b,c\) 均为正数（如果 \(x < 0\)，将 \(a,b\) 两桶互换即可）。

得到 \(xa - yb = c\) 这个等式，答案已经呼之欲出：我们只需要得到 \(x\) 个 \(a\) 桶的水，并从中去掉 \(y\) 个 \(b\) 桶的水，即可得到 \(c\) 升水。这就证明了我们的结论。

03 解法

03.00 操作步骤

具体到如何操作，从 \(xa - yb = c\) 等式中我们得到启发：

第一步，把 \(a\) 桶装满。 第二步，不断将 \(a\) 桶中的水倒入 \(b\) 桶，直到 \(a\) 桶没有水。这期间如果 \(b\) 桶装满了，将 \(b\) 桶中的水全部倒掉。如果某次操作后某个桶中恰好有 \(c\) 升水，结束。如果 \(b\) 桶倒水的次数达到 \(y\) 次且 \(a\) 桶装满 \(x\) 次，则得到 \(c\) 升水，结束。 第三步，继续第一步，重复 \(x\) 次。

第一步和第三步让我们得到了 \(x\) 个 \(a\) 桶的水，第二步我们总计倒掉了 \(y\) 个 \(b\) 桶。故最后剩下 \(c\) 升水。

解出 \(xa - yb = c\) 的方法很简单：辗转相除法，然后回代，得到 \(xa + yb = \gcd(a,b)\)，两边同乘以 \(\dfrac{c}{\gcd(a,b)}\)，最后调整符号。或者直接观察。

03.01 举例

回到开始那个问题：7L桶和13L桶，倒出4L水。

首先有 3 × 13 - 5 × 7 = 4，于是具体操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
初始状态:
第0次操作
[当前体积: 0    最大体积:13]    [当前体积: 0    最大体积:7]
一一一一一一一一一一
水池----->第1桶
第1次操作
[当前体积: 13   最大体积:13]    [当前体积: 0    最大体积:7]
一一一一一一一一一一
第1桶----->第2桶
第2次操作
[当前体积: 6    最大体积:13]    [当前体积: 7    最大体积:7]
一一一一一一一一一一
第2桶----->水池
第3次操作
[当前体积: 6    最大体积:13]    [当前体积: 0    最大体积:7]
一一一一一一一一一一
第1桶----->第2桶
第4次操作
[当前体积: 0    最大体积:13]    [当前体积: 6    最大体积:7]
一一一一一一一一一一
水池----->第1桶
第5次操作
[当前体积: 13   最大体积:13]    [当前体积: 6    最大体积:7]
一一一一一一一一一一
第1桶----->第2桶
第6次操作
[当前体积: 12   最大体积:13]    [当前体积: 7    最大体积:7]
一一一一一一一一一一
第2桶----->水池
第7次操作
[当前体积: 12   最大体积:13]    [当前体积: 0    最大体积:7]
一一一一一一一一一一
第1桶----->第2桶
第8次操作
[当前体积: 5    最大体积:13]    [当前体积: 7    最大体积:7]
一一一一一一一一一一
第2桶----->水池
第9次操作
[当前体积: 5    最大体积:13]    [当前体积: 0    最大体积:7]
一一一一一一一一一一
第1桶----->第2桶
第10次操作
[当前体积: 0    最大体积:13]    [当前体积: 5    最大体积:7]
一一一一一一一一一一
水池----->第1桶
第11次操作
[当前体积: 13   最大体积:13]    [当前体积: 5    最大体积:7]
一一一一一一一一一一
第1桶----->第2桶
第12次操作
[当前体积: 11   最大体积:13]    [当前体积: 7    最大体积:7]
一一一一一一一一一一
第2桶----->水池
第13次操作
[当前体积: 11   最大体积:13]    [当前体积: 0    最大体积:7]
一一一一一一一一一一
第1桶----->第2桶
第14次操作
[当前体积: 4    最大体积:13]    [当前体积: 7    最大体积:7]
一一一一一一一一一一
操作次数: 14

03.02 更进一步

事实上，如果使用辗转相除法，我们会得到 2 × 7 - 1 × 13 = 1，进而有 8 × 7 - 4 × 13 = 4，按照该等式仍然可以得到问题的解，但操作次数会更多。由于在 \(xa + yb = c\) 有解的情况下，解不唯一，那么问题来了，哪个解可以使操作次数最少呢？

对于等式 \(xa - yb = c\)，其中 \(x,y > 0, c < a\)，观察对应操作步骤中的每一步，在第一步到第三步的这一次循环里面，有如下的基本操作：

\(a\) 桶装满 -> \(a\) 桶倒入 \(b\) 桶 -> \(b\) 桶倒出 -> \(a\) 桶倒入 \(b\) 桶 -> \(b\) 桶倒出 -> … ->\(a\) 桶倒入 \(b\) 桶 -> \(b\) 桶倒出 -> \(a\) 桶倒入 \(b\) 桶

几乎每次循环中，均有 \(a\) 桶倒入 \(b\) 桶 的次数 = \(b\) 桶倒出 的次数 + \(1\) = \(b\) 桶倒出 的次数 + \(a\) 桶装满 的次数。最后一次循环中，最后一次把水从 \(b\) 桶中倒出是不必要的，因为这时候已经在 \(a\) 桶中得到 \(c\) 升水了，并且也不需要再把 \(a\) 桶中的 \(c\) 升水倒入 \(b\) 桶中。

故总的操作次数为 \(2\) × (\(b\) 桶倒出 的次数 + \(a\) 桶装满 的次数) - \(2\)，已知 \(a\) 桶装满 的次数 = \(x\)，\(b\) 桶倒出 的次数 = \(y\)，于是总操作次数 = \(2(x+y) - 2\)。

当 \(xa - yb = c, c > a\) 时，类似于上面的讨论，但最后必然是在 \(b\) 桶中得到 \(c\) 升水，因此总的次数 = \(2(x+y)\)。

因此，为使操作次数最少，我们应该最小化 \(x + y\)。如何使 \(xa - yb = c\) 中的 \(x + y\) 最小呢，注意到 \(xa - yb = c\) 等价于 \((x - kb)a - (y - ka)b = c\)（\(k\)为任意常数），对应的系数之和从 \(x + y\) 变成了 \(x + y - k(a+b)\)，显然我们能调整系数，使得 \(x+y\) 不超过 \(\dfrac{a+b}{2}\)，并且这也是最小的情况。（如果 \(c > a\)，考虑 \((a-y)b - (b-x)a = c\) 的情况，取最小值即可）至此我们到了最少操作次数的解。

另外遍历 \(k\) 也就遍历了所有的 \((x,y)\)，这是因为如果有 \(x_1 a - y_1 b = c\) 和 \(x_2 a - y_2 a = c\)，可以得到 \((x_1-x_2)a = (y_1-y_2)b\)，设 \((x_1-x_2)a = (y_1-y_2)b = kab\) ，易知 \((x_1 + y_1) - (x_2 + y_2) = k(a+b)\)，也就是说所有不同的 \(x+y\) 均相差 \(a+b\) 的倍数。

03.03 结论

容量为 \(a\) 升和 \(b\) 升的桶能倒出 \(c\) 升水（\(c \ne a\) 且 \(c \ne b\)），当且仅当 \(\gcd(a,b) | c\)，并且最少的操作次数为 \(2(x+y-1)\) 或 \(2(x+y)\)，其中 \(x,y > 0\) 满足 \(xa - yb = c\) 且 \(x+y \le \dfrac{a+b}{2}\)（视情况可交换 \(a,b\)）。

当 \(x+y = \lfloor\dfrac{a+b}{2}\rfloor\) 时（\(\lfloor x\rfloor\)表示不超过 \(x\) 的最大整数），最小操作次数取 \(2(x+y-1)\)，其他情况视 \(c < a\) 或 \(c > a\) 分别取 \(2(x+y-1)\) 或 \(2(x+y)\)。

04 参考文献

[1] 柯召, 孙琦. 数论讲义[M]. 高等教育出版社, 1987

05 源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
import math


def extended_euclid_algorithm(a, b):
  '''xa + yb = gcd(a, b)，返回x, y
  '''
  x, y = 1, 1
  if a < b:
    x, y = extended_euclid_algorithm(b, a)
    return y, x
  r = a % b
  if r == 0:
    return 0, 1
  # 绝对最小剩余
  if r <= math.floor(b / 2):
    x2, y2 = extended_euclid_algorithm(b, r)
    x = y2
    y = x2 - math.floor(a / b) * y2
  else:
    x2, y2 = extended_euclid_algorithm(b, b - r)
    x = -y2
    y = x2 + (math.floor(a / b) + 1) * y2
  return x, y


class Bucket:
  def __init__(self, c):
    self._max_capacity = c
    self._current_water = 0

  def get_max_capacity(self):
    return self._max_capacity

  def get_current_water(self):
    return self._current_water

  def get_remain_capacity(self):
    return self._max_capacity \
      - self._current_water

  def fill(self):
    self._current_water = self._max_capacity

  def clear(self):
    self._current_water = 0

  def pour_bucket(self, bucket):
    total = self._current_water \
      + bucket._current_water
    if (total <= bucket._max_capacity):
      bucket._current_water = total
    else:
      bucket._current_water = bucket._max_capacity
    self._current_water = total - bucket._current_water

  def __str__(self):
    return "[当前体积: %d\t最大体积:%d]" \
      % (self._current_water, self._max_capacity)


total = 0


def display_bucket(bucket1, bucket2):
  global total
  total += 1
  print("第%d次操作" % total)
  print(bucket1, bucket2, sep='\t')
  print("==========")


def solve_problem(a, b, x, y, c):
  global total
  total = -1
  bucket_a = Bucket(a)
  bucket_b = Bucket(b)
  print("初始状态: ")
  display_bucket(bucket_a, bucket_b)
  while x > 0:
    print("水池----->第1桶")
    bucket_a.fill()
    display_bucket(bucket_a, bucket_b)
    if bucket_a.get_current_water() == c \
        or bucket_b.get_current_water() == c:
      return
    while bucket_a.get_current_water() > 0:
      print("第1桶----->第2桶")
      bucket_a.pour_bucket(bucket_b)
      display_bucket(bucket_a, bucket_b)
      if bucket_a.get_current_water() == c \
          or bucket_b.get_current_water() == c:
        return
      if bucket_b.get_remain_capacity() == 0:
        print("第2桶----->水池")
        bucket_b.clear()
        display_bucket(bucket_a, bucket_b)
        y -= 1
      if y <= 0 and x <= 0:
        total -= 1
        return
    x -= 1


def main(a, b, c):
  c = min(c, max(a, b))
  d = math.gcd(a, b)
  if c % d != 0:
    print("参数错误")
    return
  temp_x, temp_y = extended_euclid_algorithm(a, b)
  temp_x *= math.floor(c / d)
  temp_y *= math.floor(c / d)
  s = temp_x - temp_y
  s = s if s > 0 else -s
  t = a + b
  q = math.floor(s / t)
  r = s % t
  flag = 1 if temp_x > 0 else -1
  if r < math.floor(t / 2):
    temp_x -= q * b * flag
    temp_y += q * a * flag
  else:
    temp_x -= (q + 1) * b * flag
    temp_y += (q + 1) * a * flag
  x, y = 0, 0
  if temp_x < 0:
    a, b = b, a
    x, y = temp_y, -temp_x
  else:
    x, y = temp_x, -temp_y
  if r == math.floor(t / 2) and c > a:
    x, y = a - y, b - x
    a, b = b, a
  # 此时 xa - yb = c，其中x,y,a,b均>0
  print("%d × %d - %d × %d = %d" % (x, a, y, b, c))
  solve_problem(a, b, x, y, c)
  print("操作次数: %d" % total)


if __name__ == "__main__":
  a, b = 5, 7
  c = 3
  main(a, b, c)
------ 本文结束 ------

版权声明

Memory is licensed under a Creative Commons BY-NC-SA 4.0 International License.
博客采用知识共享署署名（BY）-非商业性（NC）-相同方式共享（SA）。
本文首发于Memory，转载请保留出处。