Stones in Cups

An interesting problem has been posted in the Mathematics Magazine in 1992 (#1388) by Barry Cipra:

Suppose that n cups are arranged in a circle and that k stones are placed in each cup. Place your hand by one of the cups and carry out the following operation: pick up all the stones in that cup and, moving counterclockwise, drop them one at a time into the succeeding cups, leaving your hand by the cup where you dropped the last stone.

Prove that by iterating this procedure (always picking up the stones where you dropped the last stone), you will eventually wind up with all kn stones in the original cup.

In the February 1993 issue, the magazine published the following solution:

We use the term configuration to the number of stones in each cup and the position of the (empty) hand. The number of configurations (given n and k) is finite. We use the term move to refer to the redistribution of one cup's stones.

On the original configuration, and after every following move, the hand is at the cup containing one or more stones, so another (uniquely determined) move may always be made. Repeated moves will, at least eventually, cycle through a sequence of configurations.

The inverse of a move is accomplished by picking up from the currently selected cup, and then from the other cups, moving clockwise, one stone each, until an empty cup is found. All stones held are dropped into that cup. The inverse move is unique. Thus, the repeated sequence of configurations will include the original configuration.

This inverse move applied to the original configuration puts all the stones in the original cup, and will therefore be reached.

The applet below serves a playground for a generalization of the problem: a few contiguously located cups may be empty at the outset. When there are empty cups, the original position of the hand may affect the solution and, thus has been made an additional (variable) parameter of the problem. The applet lets you run iterations until "Stop" is pressed, or perform One Move at a time.

I believe the above solution is at least incomplete and may even be false. I hope the applet helps you discover why.

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?

Discussion

The solution, as it is presented in the magazine, appears to go through for the generalized problem with empty cups verbatim without any change. However, the applet helps find a counterexample to the problem's claim.

Observe that with n = 6, k = 2, one empty cup at the 6^th position and the hand at cup #1, in twelve moves the configuration rotates so that the empty cup comes to the 4^th position with the hand at cup #5 without ever getting all the stones in a single cup. From here on, the configuration simply rotates every twelve moves, so that in this case the problem does not reach the required configuration.

Late Notice: Nathan Bowler found a flaw in my reasoning. The last sentence of the proof fails when there are empty cups at the outset. Even if the problem is changed to have the stones collected in a single cup, not necessarily the original one, the sentence would fail for k > 1.

71544794