Pennies in Boxes
Here is a problem:
Suppose N pennies are randomly distributed into several boxes. Take any two boxes A and B with p and q pennies, respectively. If
(To perform an operation in the applet below click on two boxes - circles - in succession.)
|What if applet does not run?|
- G. Chang and T. W. Sederberg, Over And Over Again, MAA, 1997, pp. 27-28
We shall use the mathematical induction twice.
First, observe that in order to prove the first statement it is sufficient to prove it in the case of three non-empty boxes. If there are more, pick any three and arrange to empty one of them. As a result, you will have one less non-empty box which allows for the inductive step.
So let there be three boxes with the number of pennies x, y, z. If any two of the three numbers are equal, we may empty one of the boxes in one step. So assume that
0 < x < y < z.
Let, by the division algorithm,
Assume the binary representation of q be
q = a0 + a12 + a222 + ... + ak2k, with
Apply the operation k+1 times to either x and y or x and z. Each such operation doubles x, the content of the first box! Thus in the first box we shall successively have x, 2x, 4x, ..., 2k+1x pennies. Where will the add-on pennies come from? This will depend on the coefficients ai in (2). If the first box contains 2ix pennies and
Now assume that the total number N of pennies is a power of 2:
If n = 1, N = 2, and there are just two possibilities: the pennies are either in 1 or 2 boxes. We are immediately done in the former case, and need just one operation to empty a box in the latter.
Assume the statement is correct for N = 2k and let there be N = 2k+1 non-empty boxes. There are two possibilities: the number of pennies in each box is even, or there are boxes with an odd number of pennies. In a number of steps the latter case can be reduced to the former. Indeed, an operation on a pair of boxes with odd numbers of pennies leaves the two boxes with even numbers of pennies. (Since the total number of pennies is even, the odd boxes come in pairs.)
Now, if all the boxes contain even numbers of pennies, commit yourself to moving the pennies in pairs, for example, by gluing two pennies into a "double penny." The number of double pennies is then 2k, and we can use our assumption.