# 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 *operation*. Show that regardless of the original distribution of pennies, a finite number of such operations can move all the pennies into one or two boxes. If N = 2^{n}, pennies can be moved into a single box.

(To perform an operation in the applet below click on two boxes - circles - in succession.)

What if applet does not run? |

### References

- G. Chang and T. W. Sederberg,
*Over And Over Again*, MAA, 1997, pp. 27-28

|Contact| |Front page| |Contents| |Algebra| |Eye opener|

Copyright © 1996-2018 Alexander Bogomolny### Explanation

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

(1)

0 < x < y < z.

Let, by the division algorithm, *infinite descent* argument: if

Assume the binary representation of q be

(2)

q = a_{0} + a_{1}2 + a_{2}2^{2} + ... + a_{k}2^{k}, with _{k} ≠ 0.

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, ..., 2^{k+1}x pennies. Where will the add-on pennies come from? This will depend on the coefficients a_{i} in (2). If the first box contains 2^{i}x pennies and _{i} = 1,^{i}x pennies from the second (y) box. Otherwise, remove them from the third (z) box. The operations will always be legitimate, at least until qx pennies have been removed from y, leaving there

Now assume that the total number N of pennies is a power of 2: ^{n}.

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 = 2^{k} and let there be N = 2^{k+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 2^{k}, and we can use our assumption.

|Contact| |Front page| |Contents| |Algebra| |Eye opener|

Copyright © 1996-2018 Alexander Bogomolny