mathematics classics

Chapter 1 Irrigation Problems
problem
The classic form of the irrigation problem is this:
“假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。”

Of course, there are some reasonable restrictions outside the topic. For example, when filling water from a pond, no matter whether there is already water in the pot, the pot must be filled to the brim, and the water level in another pot cannot be compared with the "gross estimate" (We can assume that the pots are opaque and have different shapes); similarly, if you want to pour water from a pot into a pond, you must pour it all; if you want to pour water from one pot into another , and pour it all out, unless the other pot is already full during the pouring process; there is no loss of water when pouring water (evaporation overflow or something), etc.

Solution
To solve the above problem, you just use one of the two pots to fill water from the pond, pour it continuously into the other pot, and when the second pot is full, pour the water back into the pond, and repeat. After a few times, I got the answer.Take a 5-liter pot (A) filling a 6-liter pot (B) as an example: AB0050A→B0555A→B4640A→B0454A→B36.

现在我们问，如果是多于2只壶的情况怎么办（这样一来就不能用上面的循环倒水法了）？如何在倒水之前就知道靠这些壶是一定能（或一定不能）倒出若干升水来的？试举数例：（1）两个壶：65升和78升，倒38升和39升。

（2）三个壶：6升，10升和45升，倒31升。

我们可以看到，在（1）中，65=5×13，78=6×13，而39=3×13。所以如果把13升水看作一个单位的话（原题中的“升”是没有什么重要意义的，你可以把它换成任何容积单位，毫升，加仑——或者“13升”），这题和最初的题目是一样的。而38升呢？显然是不可能的，它不是13的倍数，而65升和78升的壶怎么也只能倒出13升的倍数来。也可以这样理解：这相当于在原题中要求用5升和6升的壶倒出38/39升来。

What about (2)?You will find that it is not possible to pour 31 liters of water with any two of the pots. The reason is the above, (6, 10) = 2, (6, 45) = 3, (10, 45) = 5, (here (a, b) is the greatest common divisor of a and b), and 2, 3, and 5 are not divisible by 31.But 31 liters can be poured out with three jugs: use the 10-liter jug ​​four times, fill the 6-liter jug ​​once with the 45-liter jug ​​to get 1 liter of water, then fill the 10-liter jug ​​three times to get 30 liters of water, adding up to 31 liters.

Generally we have the "watering theorem":
"If there are n pots whose volumes are A1, A2,..., An (Ai is an integer greater than 0), set w to be another integer greater than 0. Then use these n pots to pour out the full amount of w liters of water The conditions are: (1) w is less than or equal to A1+A2+...+An; (2) w can be divisible by (A1, A2,..., An) (the greatest common divisor of these n numbers)."

Both of these conditions are obviously necessary, if (1) is not met, you don't even have a place to put so much water. The principle of (2) is exactly the same as the above two pots, because in any step, there will always be water in multiples of (A1, A2,..., An) in any pot.

Now we look at sufficiency.We learned in middle school that if two integers a and b are relatively prime, then there are two integers u and v such that ua+vb=1.The method of proof is very simple: when doing Euclidean division of a and b, all intermediate results, including the final result, obviously have the form of ua+vb (for example, in the first step, assuming that a is less than b, record a The result of dividing b is s, and the remainder is t, that is, b=sa+t, then t=(-s)a+b, that is, u=-s, v=1).The mutual prime of two numbers means that the result of the last step of Euclid's rolling and dividing method is 1, so 1 can also be recorded in the form of ua+vb.To generalize a bit, if (a,b)=c, then there are u and v such that ua+vb=c (dividing both sides by c returns the original proposition).

To generalize a bit more, if A1, A2, ..., An are n integers, (A1, A2, ..., An) = s, then there are integers u1, u2, ..., Un, so that u1A1 + u2A2 + ... + UnAn = s .(*)

In algebra, this result is called "the ring of integers is the principal ideal ring".This is not difficult to prove, just see that (A1, A2, A3, A4, ..., An) = ((((A1, A2), A3), A4), ..., An).

In other words, the formula in the previous paragraph can be applied repeatedly: for example, three numbers a, b, c, their greatest common divisor is d.Suppose (a, b) = e, then (e, c) = ((a, b), c) = d.Now there are u1, u2 such that u1a+u2b=e, and v1, v2 such that v1e+v2c=d, then (v1u1)a+(v1u2)b+(v2)c=d.
Ok, let's go back to the "watering theorem". w is a multiple of (A1, A2, ..., An), according to the formula (*) in the previous section, multiplying both sides by this multiple, we have integers v1, v2, ..., vn such that: v1A1+v2A2+...+vnAn=w Note that Vi is positive and negative.

This means that as long as A1, A2, ..., press the pot, fill v1, v2, ..., vn times (if Vi is negative, "fill Vi times" should be understood as "empty-Vi times) ”), you can get w liters of water.In terms of specific operation, each Vi is calculated first, and then water is poured into the pot whose Vi is a positive number, and Vi is reduced by 1 once filled.Then put the water into the pot whose Vi is negative. When a certain pot is full, empty it, and then add 1 to the negative Vi, and pour it back and forth between the pots without changing the value of each Vi.It should be noted that to fill water from the pond, it must be filled with an empty pot, and the water to be poured into the pond must be filled with the whole pot.This continues until all Vi are 1.

Will it get stuck and can neither be filled nor poured out?Will not.If some Vi is still negative, but the Ai pot is not full: then if there is water in other pots with positive Vi, pour them all; if there is no water in other pots with positive Vi, then take that pot water to fill (don't forget to subtract 1 from the Vi of the jug that fetches water); if there is no jug with positive Vi at all - this is impossible, which means w is negative.The situation where Vi is still a positive number but the Ai pot is not full is similar to this, and you will find that you need to use the condition (1) in the theorem.

In this way, the "watering theorem" is thoroughly proved.Of course, if the number and volume of pots are relatively large in the actual problem solving, it is difficult to manually find each Ui in (*), but you can write a program to calculate even the steps of pouring water.The last thing to point out is that the Ui in (*) is not unique, so the way of pouring water is not unique either.

(End of this chapter)