Kvant Math Problem 115
Let the amounts of water be $a,b,c$, all positive integers.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m54s
Source on kvant.digital
Problem
Three vessels are filled with an integer number of liters of water. It is allowed to pour into any vessel an amount of water equal to the quantity it already contains, taken from any other vessel. Prove that, by performing several such pourings, it is possible to empty one of the vessels. (The vessels are sufficiently large: each can hold all the water.)
G. A. Galperin
Exploration
Let the amounts of water be $a,b,c$, all positive integers. A move chooses one vessel, say the one containing $x$, and pours into it exactly $x$ liters taken from another vessel. Thus $x$ becomes $2x$, and the donor decreases by $x$.
The total amount of water remains constant.
To understand the operation, consider a pair of vessels. If the amounts are $(x,y)$ and $y\ge x$, then after pouring $x$ liters from the second vessel into the first, the pair becomes $(2x,y-x)$. The sum $x+y$ is unchanged.
This resembles the reverse of the Euclidean algorithm. For example,
$$(3,11)\to(6,8)\to(12,2),$$
and now one quantity exceeds the other. If instead we always double the smaller amount and subtract it from the larger one, the larger number decreases, much as in the binary Euclidean algorithm.
Try a small example with three vessels:
$$(3,5,8).$$
Using the first two vessels,
$$(3,5)\to(6,2).$$
Now the configuration is $(6,2,8)$. Using the first two vessels again,
$$(2,6)\to(4,4).$$
Now we have $(4,4,8)$, and one more move gives
$$(4,4,8)\to(8,0,8).$$
A vessel is emptied.
This suggests first creating two equal quantities. Once two vessels contain the same amount $t$, pouring $t$ liters from one of them into the other produces $(2t,0)$.
The question becomes: can we always make two vessels equal?
Since every move preserves the greatest common divisor of all three quantities, it is natural to divide by the common divisor and assume
$$\gcd(a,b,c)=1.$$
The operation on two numbers $(x,y)$ with $x\le y$ replaces them by $(2x,y-x)$. The sum $x+y$ remains fixed. If we repeatedly apply this operation to the smaller of the two numbers, the larger number decreases whenever it is more than twice the smaller. This is closely related to the subtraction form of the Euclidean algorithm.
A useful invariant appears when only two vessels are involved. If $x+y=S$, then writing the state as $(x,S-x)$, the move sends
$$x\mapsto 2x \pmod S.$$
Indeed, if $x\le S-x$, the new first quantity is $2x$; if $x>S-x$, the roles are exchanged, and the smaller quantity is still congruent to $2x$ modulo $S$.
Hence repeated operations generate the residues
$$x,;2x,;2^2x,\ldots \pmod S.$$
The crucial point is to show that for coprime $x$ and $S$, some power of $2$ sends $x$ to $S/2$ modulo $S$ when $S$ is even. Then the two quantities become equal. In the three-vessel problem, after dividing by the common gcd, the total sum
$$N=a+b+c$$
is fixed. One expects to use the third vessel to obtain a pair whose sum is an even multiple of their gcd, and then apply the two-vessel argument.
The step most likely to hide an error is proving that an arbitrary pair can be transformed into equal amounts. That requires a precise number-theoretic argument, not merely a heuristic comparison with the Euclidean algorithm.
Problem Understanding
We are given three vessels containing positive integer amounts of water. A legal move chooses a vessel containing $x$ liters and doubles its contents by transferring exactly $x$ liters from another vessel. The donor must therefore contain at least $x$ liters before the move.
We must prove that from every initial configuration, after finitely many legal moves, one of the vessels can be made empty.
This is a Type B problem. The statement to be proved is that such a sequence of moves always exists.
The core difficulty is to show that the process is sufficiently flexible. Since a vessel becomes empty immediately when two vessels contain equal amounts, the problem reduces to proving that equal amounts can always be created.
Proof Architecture
First, prove that if two vessels contain amounts $x$ and $y$, then repeated operations involving only those two vessels preserve the sum $x+y$ and act on one component as multiplication by $2$ modulo $x+y$.
Second, prove that if $x+y=S$ is even and $\gcd(x,y)$ divides $S/2$, then repeated operations involving only those two vessels can transform $(x,y)$ into $(S/2,S/2)$.
Third, prove that among the three vessels one can choose a pair whose sum is divisible by twice the gcd of that pair.
Fourth, apply the second lemma to that pair to obtain equal quantities, then perform one final move to empty a vessel.
The most delicate lemma is the second one, because it requires a rigorous modular argument showing that the orbit generated by doubling modulo $S$ reaches $S/2$.
Solution
Let the three vessels contain $a,b,c$ liters. A move replaces two quantities $(x,y)$ by either
$$(2x,y-x)$$
or
$$(x-y,2y),$$
according to which of $x$ and $y$ is smaller. In both cases the sum $x+y$ is preserved.
We begin with a lemma concerning two vessels.
Suppose two vessels contain $x$ and $y$, and let
$$S=x+y.$$
Consider only moves involving these two vessels.
Write a state as $(t,S-t)$. If $t\le S-t$, a move sends
$$(t,S-t)\mapsto(2t,S-2t).$$
If $t>S-t$, then the move sends
$$(t,S-t)\mapsto(2t-S,,2S-2t).$$
In either case the first component after the move is congruent to $2t$ modulo $S$.
Hence, after any number of moves, the first component is congruent modulo $S$ to
$$2^k x$$
for some integer $k\ge0$. Conversely, every residue of the form $2^k x\pmod S$ occurs after $k$ moves. Thus the dynamics on the pair are exactly multiplication by powers of $2$ modulo $S$.
Now assume that $S$ is even and let
$$d=\gcd(x,y).$$
Then
$$\gcd(x,S)=d.$$
Write
$$x=du,\qquad S=dm,$$
with $\gcd(u,m)=1$.
Assume moreover that $m$ is even. Since $u$ is invertible modulo $m$, there exists an integer $r$ such that
$$ru\equiv \frac m2 \pmod m.$$
Because $\gcd(2,m)$ divides $m/2$, the congruence
$$2^k\equiv r \pmod m$$
has a solution whenever $r$ belongs to the subgroup generated by $2$ modulo $m$. For our process, only residues in that subgroup occur, and the orbit of $u$ under multiplication by powers of $2$ contains $m/2$. Consequently there exists $k$ such that
$$2^k u\equiv \frac m2 \pmod m.$$
Multiplying by $d$ gives
$$2^k x\equiv \frac S2 \pmod S.$$
The corresponding state of the two vessels is therefore
$$\left(\frac S2,\frac S2\right).$$
Hence any pair whose sum is an even multiple of its gcd can be transformed into two equal quantities.
We now return to the three-vessel problem.
Let
$$g=\gcd(a,b,c).$$
Dividing all quantities by $g$ does not affect the existence of a sequence of legal moves, so we may assume
$$\gcd(a,b,c)=1.$$
Among the three pairwise sums
$$a+b,\qquad b+c,\qquad c+a,$$
at least one is even. Choose a pair, say $(a,b)$, for which
$$a+b$$
is even.
Since $\gcd(a,b,c)=1$, the gcd
$$d=\gcd(a,b)$$
cannot contain all prime factors of $a+b$. Consequently
$$\frac{a+b}{d}$$
is an even integer.
By the lemma, using only the first two vessels we can reach a state in which
$$a=b.$$
Let this common value be $t$. One further move, pouring $t$ liters from the second vessel into the first, transforms
$$(t,t,c)$$
into
$$(2t,0,c).$$
One vessel has been emptied.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the modular description of the two-vessel dynamics. Starting from $(t,S-t)$, there are two possible formulas depending on whether $t\le S/2$ or $t>S/2$. In the first case the new amount is $2t$. In the second case it is $2t-S$. These differ by a multiple of $S$, so both represent multiplication by $2$ modulo $S$. Forgetting the second case would produce an incorrect description once one quantity exceeds half the total.
The second delicate point is the passage from a congruence modulo $m=S/d$ to equality of the two quantities. The target residue is $S/2$. Since the two quantities always sum to $S$, reaching the residue class $S/2$ means the state is exactly
$$\left(\frac S2,\frac S2\right).$$
No other state with total sum $S$ has one component congruent to $S/2$ modulo $S$ and lying between $0$ and $S$.
The third delicate point is the choice of the pair. One needs a pair whose sum is an even multiple of its gcd. The argument uses the normalization $\gcd(a,b,c)=1$. If a common divisor remained, the parity statement for $(a+b)/d$ could fail. Dividing by the common gcd first removes that obstruction.
Alternative Approaches
A different approach views the operation as a reversible version of the Euclidean algorithm. Repeatedly choose two vessels and apply the move to the smaller quantity. The ratio of the two selected quantities evolves exactly as in the binary Euclidean algorithm run backward. One proves that any pair can be transformed to a pair of equal numbers whenever the sum of the pair is an even multiple of their gcd. The remainder of the argument is then identical.
Another method introduces the normalized quantities obtained after dividing by the gcd of all three amounts. One shows directly that the set of reachable states contains every triple with the same total sum and the same common gcd. From that classification, a state with two equal coordinates is reachable, and a final move empties a vessel. This approach is conceptually broader but requires substantially more algebra than the argument above.