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.
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 = 2km, where m > 1 is odd. Choose such an initial distribution of water as to have every jug contain a multiple of 2k. It is always possible by, say, having 2k in one jug and 2k(m - 1) in some other. Whatever takes place afterwards, each of the jugs will contain a multiple of 2k pints. Before the very last pouring, there will be two jugs with equal amounts of water, say 2ks. After the last pouring, one of the jugs will contain 2ks + 2ks = 2k+1s of water. But this is impossible because then
2km = n = 2k+1s,
making m even. A contradiction.
(The problem admits a converse.)
|Contact|
|Front page|
|Contents|
|Arithmetic|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
