Using your Head is Permitted

January 2010 solution

Part 1:

Consider for a moment only the n-1 left-most positions, ignoring the right-most volume. For each of these positions, if the volume currently in this position is in its correct place, mark this with a "1". If it is out of place, mark it with a "0". This constructs a string of n-1 zeros and ones, which can be read from left to right as an n-1-bit integer.

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:

  1. Find the right-most "0" value.
  2. Switch it to a "1".
  3. Switch all elements to its right from "1" to "0".
Because only one element is switched from "0" to "1", this gives us immediately the position to which Larry moved a volume. Because all elements to the right of this position were already in place, none of them could have been the volume that Larry moved. Larry therefore must move the right-most volume on the shelf (the one that isn't encoded by a binary digit at all). So, we also have a unique solution to the position from which Larry moved a volume.

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.

Part 2:

Laura's strategy does guarantee that the volumes will ultimately be sorted. To prove this, consider that in every situation other than when the volumes are all correctly sorted, Laura has at least one legal move to make. This means she cannot get "stuck" in any position. If there is any case where the strategy does not lead to the volumes ultimately becoming sorted, this case must be a set of positions that completes a cycle. We shall prove that no such cycle exists.

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