# Many Jugs to One I

Several jugs are given (at least two) with a total of 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. It is known 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. Prove that n is a power of 2.

This is a problem from a Bulgarian 1989 winter competition. The proof below, by Miroslav Petkov, was awarded a special prize.

### References

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

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

Copyright © 1996-2018 Alexander Bogomolny

Several jugs are given (at least two) with a total of 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. It is known 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 avilable water. Prove that n is a power of 2.

### Proof

Assume on the contrary that n = 2^{k}m, where m > 1 is odd. Choose such an initial distribution of water as to have every jug contain a multiple of 2^{k}. It is always possible by, say, having 2^{k} in one jug and 2^{k}(m - 1) in some other. Whatever takes place afterwards, each of the jugs will contain a multiple of 2^{k} pints. Before the very last pouring, there will be two jugs with equal amounts of water, say 2^{k}s. After the last pouring, one of the jugs will contain 2^{k}s + 2^{k}s = 2^{k+1}s of water. But this is impossible because then

2^{k}m = n = 2^{k+1}s,

making m even. A contradiction.

(The problem admits a converse.)

[an error occurred while processing this directive]

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

Copyright © 1996-2018 Alexander Bogomolny