Problem:
In the hold of a pirate ship are ten treasure chests lying on pedestals in a circular arrangement. The captain would like to move each chest clockwise by one pedestal. However, the chests are so heavy that the captain and his assistant can only switch two chests at a time. What is the minimum number of switches needed to accomplish the task?
Solution:
The answer is . It is easy to see that nine moves are sufficient; they can move a single chest counterclockwise one pedestal at a time, until after nine moves all of the other chests have been moved clockwise one pedestal.
Suppose that, at each stage of the game, we draw an arrow from each pedestal to the pedestal on which the chest which it now holds originally sat. Then every pedestal has one incoming and one outgoing arrow, and the overall graph can be decomposed into some number of disconnected cycles. Let be the number of cycles. We note that at the beginning of the process, (every arrow is its own cycle) while at the end, (all the pedestals are connected in a ring).
We now claim that at each move, cannot decrease by more than . Each move affects only two pedestals, which may initially belong to one or two cycles; the performance of the move may fuse two cycles into one or break up cycles into more cycles, but it certainly cannot replace two cycles by zero cycles. Therefore, decreases by at most at each move and hence cannot reach as low as before the ninth move.