It is easy to verify that any move that Larry makes must necessarily increase this number. Because the number's lowest possible value is zero, its highest possible value is 2n-1-1 and its minimum increment is one, this bounds the number of days that Larry's strategy can possibly last to be a maximum of 2n-1-1 days.
This maximum can actually be reached. To find the initial position and the path that is needed to reach this maximum, consider that in each move the indicator number must be incremented exactly by one. Incrementing a binary-encoded natural by one involves the following procedure:
Combining these two facts together, we know that there is only a unique choice for Larry's move at any given day, if his strategy is to last 2n-1-1 days. We can therefore work backwards in time, starting with the sorted encyclopedia and working backwards according to Larry's move of choice until we reach the initial position 2n-1-1 moves earlier.
The solution is that the unique initial sorting that allows Larry's strategy to last as long as it can last is when the volumes are arranged from left to right by the following order: n, 1, 2, 3, ...., n-1. From this position, the unique solution for Larry's choice of moves (in order for the strategy to last as long as it can) is to always pick the volume of the encyclopedia that is currently right-most.
Let us assume on the contrary. Suppose that a cycle exists, and that volume k is picked by Laura at some point during it. W.l.o.g., let us assume that k is moved to the right. For the cycle to complete, k must at some point move from its current position (position k from the left) back to its original position, so more to the left. This necessarily involves it being shifted from position k from the left to position k-1 from the left by a step in which some other volume, m, is moved to the right. Note that the volume number m must be greater than k. Pick k to be the highest volume number to travel to the right, and the contradiction is evident.
Back to riddle
Back to main page