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

  1. 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 = 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|

Copyright © 1996-2018 Alexander Bogomolny

71471684