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 p ≥ q you are allowed to remove q pennies from box A and put them into box B, and this action is called an 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ⁿ, pennies can be moved into a single box.

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

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

Explanation

References

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

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, y = qx + r, where 0 ≤ r < x. We'll show that by a finite number of operations it is possible to make one of the boxes (in fact, the second one) contain r pennies. The assertion will then follow by the infinite descent argument: if r ≠ 0, continue to apply the same procedure to reduce the latter. Since there is only a finite number of non-negative integers less than a given x (or r) the process can't go on indefinitely, i.e. the infinite descent is not possible, but the only way for it to stop is to reach the case when the remainder in the division algorithm vanishes. (The impossibility of the infinite descent is equivalent to applying mathematical induction.) Thus, let's see what can be done with the configuration (1).

Assume the binary representation of q be

(2)

q = a₀ + a₁2 + a₂2² + ... + a_k2^k, with a_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+1x 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ⁱx pennies and a_i = 1, remove 2ⁱ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 r < x pennies, as desired.

Now assume that the total number N of pennies is a power of 2: N = 2ⁿ. We'll show that in this case the pennies can be collected into a single box. The induction is by 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.

What Is Infinite Descent?

71535191