You say 'The solution, as it is presented in the magazine, appears to go through for the generalized problem with empty cups verbatim without any change.', but this is not quite true. In fact, everything but the final line goes through unchanged. Indeed, you have shown that in the specific case you consider, 'the repeated sequence of configurations will include the original configuration.'

The final line states that 'This inverse move applied to the original configuration puts all the stones in the original cup, and will therefore be reached', but in the similar case you consider, applying the inverse move to the original configuration does not put all the stones in the original cup.

I like the proof.

Thankyou

sfwc
<><

You are right. I've been thinking of the problem of collecting all the stones into 1 cup and not necessarily the original one.

So what I've been thinking of is this replacement for the last sentence

"This inverse move applied to the original configuration puts all the stones in a single cup (which happens to be the original one), and will therefore be reached."

But this, too, is only true when k = 1. For k > 1, the empty space is reached too soon. A pity.

First I need to set up some notation. For simplicity, I shall initially work with an infinite collection of cups, one for each integer, and finitely many stones. Evidently, for any initial configuration, a situation will eventually be reached in which your hand is to the right of all but one of the stones, and all remaining moves consist of picking up that stone and moving it to the next cup along.

I shall use the term 'arrangement' to refer to a specification of the number of stones in each cup, independently of the position of the hand. So an arrangement may be thought of as a function from the integers to the natural numbers. For an arrangement u define s_n(u) by s_n(u)(k) = u(k-n); s_n has the effect of shifting all stones k places to the right.

To simulate the fact that the real problem refers to a loop, I shall consider the effect on an arrangement of having the hand approach from infinity on the left moving a single stone in the manner described above, and change the arrangement of the stones by following the rules until it leaves all but one stone to its left and goes to infinity on the right with the remaining stone; I shall call the effect that this has on an arrangement a rearrangement. Obviously a rearrangement does not change the total number of stones.

I shall say an arrangement u is confined by {a, b} if u(c) > 0 => a <= c <= b.

Define u(n, 0) to be the arrangement with n stones in cup 0 and none elsewhere. Define u(n, i) inductively by letting u(n, i + 1) be the rearrangement of u(n, i).

Lemma: Let n <= 2^t. Then u(n, i) is confined by {i, i + n - 1} and u(n, 2^t) is the arrangement with all n stones in cup 2^t (That is, it is s_{2^t}(u(n, 0))
Proof: Induction on t.
There are 2 cases:

Case 1: n < 2^(t-1).
Then u(n, 2^(t-1)) = s_{2^(t-1)}(u(n, 0)), so for any i u(n, 2^(t-1) + i) = s_{2^(t-1)}(u(n, 0)). In particular, u(n, 2^t) = s_{2^(t-1)}(u(n, 2^(t-1))) = s_{2^(t-1)}(s_{2^(t-1)}(u(n, 0))) = s_{2^t}(u(n, 0)).
u(n, i) is confined by {i, i + n - 1} by the induction hypothesis.

Case 2: n > 2^(t-1). Let k = n - 2^(t-1).
Then u(n, 1) = u(2^(t-1), 1) + s_{2^(t-1)}(u(k, 1))
Now, as u(2^(t-1), 2^(t-1)) = s_{2^(t-1)}(u(2^(t-1), 0)), for i <= 2^(t-1) + 1, u(2^(t-1), i) is confined by {i, 2^(t-1)} and s_{2^(t-1)}(u(k, i)) is confined by {2^(t-1) + i, n + i - 1} so that u(n, i) = u(2^(t-1), i) + s_{2^t-1}(u(k, i)).
Therefore by the induction hypothesis u(n, 2^(t-1)) = s_{2^(t-1)}(u(2^(t-1), 0)) + s_{2^t}(u(k, 0)).
Now the first 2^(t-1) rearrangements from u(2^(t-1), 0)) each add one stone to cup 2^(t-1). Thus for 0<= i <= 2^(t-1) we have u(n, i + 2^(t-1)) = s_{2^(t-1)}(u(2^(t-1), i)) + s_{2^t}(u(k, 0)).
In particular, u(n, 2^t) = s_{2^t}(u(2^(t-10, 0)) + s_{2^t}(u(k, 0)) = s_{2^t}(u(n, 0)).
The confinement condition is similar, but simpler.

Now consider the original problem. The starting configuration is just like u(n-1, 1) with the blank spaces erased, the ends joined, and the hand just about to reach the arrangement from the left hand side. The confinement conditions ensure that the evolution is exactly as in the lemma: For 2^t > n-1, the stones will all be in a single cup after 2^t - 1 rearrangements. Each rearrangement involves at most n moves, and the whole cycle need be repeated at most n times to bring all the stones into the original cup. So as 2^t < 2n - 2, the total number of moves in the cycle is O(n^3), which is much shorter than would be expected from the given proof.

This argument does not appear to generalise for k>1,

Thankyou

sfwc
<><