Three Jugs - Equal Amounts

Three jugs are given with a total of 3·2n pints of water. Each jug not empty and contains an integer amount of pints. We may pour into any jug as much water as it already contains, from any other jug with a greater amount of water. Prove that, with one exception, it is possible after a series of such pourings to have the same amount of water in all three jugs.

Proof

|Contact| |Front page| |Contents| |Arithmetic| |Math induction|

Copyright © 1996-2017 Alexander Bogomolny

Three jugs are given with a total of 3·2n pints of water. Each jug not empty and contains an integer amount of pints. We may pour into any jug as much water as it already contains, from any other jug with a greater amount of water. Prove that, with one exception, it is possible after a series of such pourings to have the same amount of water in all three jugs.

Proof

The proof is by induction on n. The statement is clearly true for n = 1. Assume it holds for n = k and let there be 3·2k+1 pints of water distributed among several jugs. We shall first show that, excluding one exceptional distribution of water, it is always possible to get even amounts of pints in all three jugs.

If there are jugs with an odd amount of pints, there must be 2 of them. There are two possibilities. Let the odd amounts be a (in jugs A1 and A2) and the remaining even one b (in jug B).

If a < b, pour from B to, say, A1 to obtain distribution of even numbers 2a, a, b - a. If the new configuration is different from (a, a, b), we made a progress. Otherwise we stalled. The latter unfortunate circumstance occurs when b - a = a, or, which is the same, 2a = b. This is the exception mentioned in the body of the problem. Provided 2a ≠ b, we may perform one additional step to either (2a, 2a - b, 2(b - a)) or (2a, 2a, b - 2a), with all amounts even.

If a > b, move from the distribution (a, a, b) to (a, a - b, 2b). A repetition of the previous configuration is not possible. For then we would have a = 2b, meaning that the total amount of water is 2b + 2b + b = 5b pints, which contradicts the premise that the total is 3·2k+1. On the next pouring, move to (b, 2(a - b), 2b), with all amounts even.

Once all the jugs contain even amounts of water, we may imagine the pint unit increased by a factor of two, making the total 3·2k of "big" pints and reducing the case to the inductive assumption.

The only exceptional case where the argument does not work is the configuration (a, a, 2a), for which 4a = 3·2k+1. The argument also shows that, unless we start with the exceptional case, it is always possible to avoid it, thus completing the inductive argument and ultimately solving the problem.

Now note that we came across the exceptional case (a, a, 2a) while looking for the distributions with two jugs having two equal odd amounts of water. What we found in fact, is that of itself this situation is not necessarily unsolvable (actually (3, 3, 6), i.e., for n = 2, is the only such case.) However, the configuration (a, a, 2a) may only lead to the permutations of itself, (2a, a, a) and (a, 2a, a) and is, therefore never solvable.

To sum up, the problem is solvable for the total of 3·2n pints of water, unless the initial distribution is (3·2n-2, 3·2-2, 3·2n-1), for n ≥ 2. It is always solvable for n = 1.

As an example, let's have three jugs A, B, C with amounts of water (7, 7, 10), for n = 3. I show one sequence of moves in the table below:

ABC 
7710 
7143C→B
7116B→C
11112A→C
1221C→B
2211B→A
2202B→C
4182B→A
4164B→C
8124B→A
888B→C

What could be a converse theorem?

|Contact| |Front page| |Contents| |Arithmetic| |Math induction|

Copyright © 1996-2017 Alexander Bogomolny

 62645571

Search by google: