Consider an n-1 bit long non-negative integer, X, whose ith digit (starting with the MSB being i=1) is 0 if and only if volume i is too far to the right.
Each time Laura moves any volume to the left (pushing other volumes to the right in order to give it room), X is strictly increased. When Laura moves a volume to the right, X may increase or it may remain the same, but it cannot decrease.
Consider, now, a similarly defined n-1 bit long non-negative integer, Y, whose ith digit is 0 if and only if volume n+1-i is too far to the left. (Again, counting from the MSB being i=1.)
Y is strictly increased when Laura moves any volume to the right. It is not decreased when Laura moves a volume to the left.
A simple solution to part 2 of the January riddle would therefore have been to take X+Y as a potential function that is increased at each step. Because its range is between 0 and 2(2n-1-1), this gives an upper bound on F(n), proving that it can't go to infinity.
This bound is not tight, however, due to several constraints imposed on X and on Y: if bit i of X [which we shall henceforth denote X(i)] and bit j of Y both refer to the same volume, one asserting whether it is too far to the right, the other asserting whether it is too far to the left, then
First, note that if either volume 1 or volume n is in its place then the problem is reduced to a problem of size n-1, after which only F(n-1) steps are allowed. Let us, therefore, consider how many steps Laura's strategy can last without placing either volume 1 or volume n in place. In this scenario, both X and Y are integers with only k=n-2 bits.
Let us now divorce the X-Y problem entirely from its encyclopedic origins, and consider it as its own problem. The problem is as follows:
Let X and Y be two k bit long non-negative integers. We play a game in which at each step we increase either X or Y, potentially both, (but decreasing neither) pursuant to the following rules. The bits of X and Y are connected in pairs, the LSB of X with the MSB of Y, the second-least significant bit of X with the second-most significant bit of Y, and so forth until the MSB of X and the LSB of Y. Within each such <i,j> pair the following two restrictions must always hold:
In order to find the exact value of G(k), first note that at most G(k-1) steps can elapse until both MSBs are equal 1. The reason for this is that if the MSB of either variable is zero then the LSB of the other variable is 1, and by removing these two bits we end up with an equivalent problem one size smaller.
From the point in which both MSBs are 1, the MSBs can no longer change. The LSBs, however, are no longer restricted by any pairing rules. Let us define X' to be X without its MSB and LSB, and let us define Y' correspondingly. The game reduced to X' and Y' is the same game, only two sizes smaller. Additionally, there may be moves that affect only the LSBs of X and Y without causing any change to X' and Y'. Let us bound the number of these moves.
We've established that the number of steps that change the values of either X' or Y' is bounded by G(k-2). We can make a stronger statement that the number of steps that change X' plus the number of steps that change Y' is still bounded by G(k-2). In order to prove this, suppose for some sequence of X'-Y' steps this is not true, simply take each step where both X' and Y' are changed together and make it into two steps, the first changing only X' and the second changing only Y'. These steps remain legal steps in the game. If this sequence is now greater than G(k-2) steps in length, this contradicts the definition of G.
So, we know that the number of steps that change X' plus the number of steps that change Y' is bounded by G(k-2). We further know that only when X' changes can the LSB of X change from 1 to 0 (or else this would have resulted in a decrease in the value of X). This bounds the number of such LSB changes for X from 1 to 0 to some value. Let us call this value a. A similar statement can bound the number of LSB changes for Y from 1 to 0 to some value, b where a+b≤G(k-2).
The number of LSB-only moves can therefore be bounded by the number of times the LSB of X could have switched from 0 to 1 plus the number of times the LSB of Y could have switched from 0 to 1.
If both LSBs begin as 0, the total number of LSB switches from 0 to 1 is bounded by G(k-2)+2, meaning that the total number of steps starting from when both MSBs became 1 is bounded by 2G(k-2)+2. However, this also means that the MSBs were never 0 to begin with: no move can switch an MSB from 0 to 1 while simultaneously switching the paired LSB from 1 to 0. This violates the motion constraints on X and Y. The total number of steps in this alternative for the entire X-Y game is therefore relatively low: 2G(k-2)+2.
The other alternative is that at least one LSB began as 1. This means that the total number of LSB switches from 0 to 1 is bounded by G(k-2)+1, the total number of steps from the point in which the MSBs both became 1 is bounded by 2G(k-2)+1, and the total number of steps in the entire X-Y game is bounded by G(k)≤G(k-1)+1+2G(k-2)+1.
Combining this with the initial values for k=1 and k=2 we reach the closed-form formula G(k)≤2k-1.
Now, we can conclude the proof by recalling that F(n)≤F(n-1)+1+G(n-2). With the initial values for n=1 and n=2 we reach the closed-form formula F(n)≤2n-1-1.
Laura can therefore not make even a single move more than Larry, and the longest-case already cited in the solution to Larry's problem is also the longest-case for Laura.