Three jugs are given, each containing an integer amount of pints of water. It is allowed to pour in any jug as much water as it already contains, from any other jug with a greater amount of water. Prove that after several such pourings it is possible to empty one of the jugs. (Assume that the jugs are sufficiently large; each capable of holding all the water available.)

This problem was posed for the 1971 All-Union Math Olympiad (USSR).

Solution

Label the jugs A, B, C and let them contain a, b, c pints of water, respectively, where 0 \le a \le b \le c. It suffices to show how to obtain less than a pints of water in one of the jugs, that is, less than than the minimum of the numbers a, b, c. Indeed, if such reduction is always possible, we could then iterate and keep reducing the minimum number of pints in the three jugs. But a decreasing sequence of integers can't be infinite and, in our case, has to stop at 0 for, otherwise, the process could continue.

Let b = qa + r, where 0 \le r < a. Note that q > 0 because b \ge a. We are going to prove that it is possible to pour qa pints from B to A (possibly with intermediate pourings from C to A) so that at the end B will contain r (< a) pints of water, solving the problem.

Let q = 2^{i_0}+2^{i_1}+\cdots+2^{i_n} be the binary expansion of q, 0 \le i_0 \le i_1 \le \cdots \le i_n. Then the content of C may be thought of as consisting of portions with volumes 2^{i_0}a, 2^{i_1}a, \cdots, 2^{i_n}a, r. In general, some of the numbers out of 0, 1, \cdots, i_{n}-1 may be missing from the expansion of q. Denote the missing numbers j_1, j_2, \cdots, j_k. It is clear that c exceeds the total of the missing binaries, viz., c \ge \sum_{m=1}^{k}2^{j_m}a, because \sum_{m=1}^{k}2^{j_m}a \lt (2^{i_n}-1)a \le b \le c.

If so, we can pour successively all portions 2^{i}a, i = 0, \cdots, i_n into A taking some from B and some from C until B contains r pints of water.

Alternate Solution from Graph Theory (Stuart Mark Anderson)

Consider the values a, b, c to be the coordinates of a point in 3-space. The pouring operations allow one to move to any of three other points, (2a, b-a, c), (2a, b, c-a), or (a, 2b, c-b), and these points will be distinct if a, b, c are distinct and positive. Similarly, one may arrive at (a, b, c) from (a/2, b-a/2, c), (a/2, b, c-a/2), or (a, b/2, c-b/2), provided that a, b are even. Therefore the points and pouring operations form a directed graph G lying in the plane x+y+z = \text{constant}.

Every vertex with less than 3 departing edges either is a solution or has 2 values equal, and so leads to a solution in one step. Thus the goal is to show that for any vertex V there is a path leading to a vertex with less than 3 departing edges.

For an arbitrary vertex V, let S_V by the maximal subgraph reachable from V, and assume that every vertex in S_V has 3 departing edges. Since each of these must lead back into S_V by maximality, each vertex must also have 3 arriving edges, by the pigeon-hole principle. (Incidentally, S_V is therefore a connected component, since no edges may arrive from outside, as the arriving edges are all accounted for.)

However, this is absurd: every vertex in S_V must then have even values for (a, b, c); for the smaller values must be even, and if the largest is odd, it can be reduced by pouring until it is no longer the largest, yet remains odd. Hence one may divide all values by 2 ( repeatedly if necessary) and arrive at another graph isomorphic to S_V with some odd values, therefore with some vertex of less than 2 departing edges, which is a solution. Doubling the values along this path lifts it to a path in S_V, solving the original problem.

References