Solution
I received answers and solutions from several, including Bruce Torrence, Stephen Dupal, Joseph DeVincentis, Jim Tilley, Al Zimmermann, and Jeff Boersema.
Note that there are three possible interpretations of "initial position." The intent, which the solvers used, was that the chairs should appear anywhere on the cable, and anywhere in space, in the same cyclic order they started in: 1, 2, 3,..., N. One could also insist that they appear in this order and in the same location in space (i.e., with 1 and 2 ready to be loaded). Or one could ask that they be in the same order in the exact spot on the cable that they started in.
(As I write this, I realize there is a fourth: that they be in cyclic order, in the exact spot on the cable they started in, and in the exact location in space. It's all relative! Of course, when one is on the lift one has no idea where on the cable a chair is ...)
I will focus here on the first interpretation, that they be in cyclic order anywhere on the cable and anywhere in space. In fact, this can only happen if their location in space is identical to the initial state.
Consider the initial location of chair i in space to be slot i. Then whenever things change or move, we have a permutation. For N = 107, we start in the identity permutation, given in list form as {1, 2, ..., 107}. After the first loading of two chairs, the permutation is {3, 4, 5, 6, ..., 106, 107, 2,1}, because 1 has moved into slot #107, and 3 into slot #1. This permutation, written in cycle form, is C = (1 3 5 7 ... 107)(2 4 6 8 ...).
Since the same thing happens at each double-loading, the first question is: what is the least m so that Cm is the identity? Because (for general odd N) the odd cycle has order (N + 1)/2 and the even has order (N − 1)/2 and these numbers are coprime, the order of C is their product, or (N² − 1)/4.
But since each loading step loads two chairs, this means that the number of chairs that must be loaded is (N² − 1)/2. It takes 12 seconds for a double-load step.
So, with N = 107, it takes 9.54 hours to return to the initial cycle, or a little less than once a day. The number of full loops made by the cable is (N² − 1)/(2N), or 53.4953.
Now we must ask if it is possible for the numbers to be in the initial order, but not in the initial position. In fact, this cannot happen. Here is Bruce Torrence's proof of that:
N is odd. Let s = (135 ...)(246 ...) in cycle notation. Let m = (N² − 1)/4, the number of loading steps to get the identity. For example, N = 5 means m = 6. This is the order of s.
Because N is odd, we have that gcd(m, N)
= gcd((N − 1)/2, N) * gcd((N + 1)/2, N)
= gcd((N − 1) (N + 1), N)
= 1
Now suppose sj = (123 ... N)k, which encodes a rotated (by k) version of the identity. Then s(N j) = identity. So N j is a multiple of m; and therefore, by the gcd comment, j is a multiple of m. So sj is the identity and not a nontrivial rotation of it.
There are other things to investigate in this problem. Of course, there are the variations mentioned above. But sticking to the primary interpretation, poser Kim Ruhland also wanted to know this problem inspired by a physical question: If one can see the number X on one's own chair and the number Y on the chair one is looking at (and N is known and odd), can one say whether one is moving closer to the initial state or farther from it? More generally, how much does one have to see (X, Y, Z on the chair in front of Y, W in front of Z, ...) in order that one can answer this question.
I made some initial investigations and think I know the answer experimentally. Often knowledge of X and Y is enough. But not always.
[Back to Problem 1232]
© Copyright 2017 Stan Wagon. Reproduced with permission.