# 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 2^{n-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 2^{n-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:

- Find the right-most "0" value.
- Switch it to a "1".
- 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
2^{n-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 2^{n-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