# Many Jugs to One II

^{n}pints of water, each jug containing 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, regardless of the initial distribution of the water in jugs, it is possible after a series of such pourings to empty all of them but one, which then will contain all the available water.

(The is a converse of another problem.)

### References

- S. Savchev, T. Andreescu,
*Mathematical Miniatures*, MAA, 2003

|Contact| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny

^{n}pints of water, each jug containing 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, regardless of the initial distribution of the water in jugs, it is possible after a series of such pourings to empty all of them but one, which then will contain all the available water.

### 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 2^{k+1} pints of water distributed among several jugs. The number of the jugs that contain an odd amount of pints must be even. Arrange them in pairs and pour from one jug in a pair into another. This will make the number of pints in each of the given jugs even. From then on every jug will contain an even number of pints.

The problem is then equivalent to the one where the jugs contain half of what they contained on the previous stage to the total of 2^{k}. By the inductive assumption, there is a sequence of pourings that leaves a single jug with all the water and other jugs empty.

Returning to the original configuration, we may simply repeat the same sequence of pourings but with twice the amount.

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

Copyright © 1996-2018 Alexander Bogomolny