Solution to Math Puzzle

A few days a go I posted a math termination puzzle. There was one reply with the draft of a solution, so now I am posting the solution from Communications of the ACM here. It is a little involved, so beware. Here it is:

Let x0, x1, x2, x3, x4 be the five numbers. summing to s > 0, with indices taken modulo 5. Define a doubly infinite sequence z by z0 = 0 and zi = zi-1 + xi. The sequence z is not periodic, but it is periodically ascending; z5 = zi + s. In the example, the x values are 2, 4, -3, 1, -3; s = 1; and the z sequence is:

... -2 0 4 1 2 -1 1 5 2 3 0 2 6 3 4 1 3 7 4 5 2 4 8 5 6 ...

where the leftmost 0 represents z0.

If xi is negative, zi < zi - 1 and flipping xi has the effect of switching zi with zi - 1, they are now in ascending order. Simultaneously, it does the same for all paris zj, zj - 1 whose indices are shifted from them by multiples of 5. Thus, flippling labels amounts to sorting z by adjacent transpositions.

Tracking the progress of the sorting process needs a potential function Phi to measure the degree to which z is out of order. Let i+ be the number of indices j > i for which zj < zi; note i+ is finite and depends only on i modulo 5. We let Phi be the sum 0+ + 1+ + 2+ + 3+ + 4+.

When xi+1 is flipped, i+ decreases by 1, and every other j+ is unchanged, so Phi decreases by 1. When Phi hits 0 the sequence is fully sorted so all labels are non-negative and the process must terminate.

We conclude that the process terminated in exactly the same number (the initial value of Phi) of steps regardless of choices, and the final configuration is independent of choices. The reason is there is only one sorted version of z. Moreover, the proof works with 5 replaces by any integer greater than 2.

So, there you have it. A very interesting solution, the key here is the function Phi, which decreases by 1 after every flipping, because of the way the sequence was constructed :-) Very nice. I must confess that I wasn't going this way about it. My Phi function was turning more complicated, but the real trick here is the sequence, which transform the problem into a sorting problem, simplifying the Phi function quite a bit.