IMO 1998 SL 24

Origin: SWE

Problem

Cards numbered 1 to 9 are arranged at random in a row. In a move, one may choose any block of consecutive cards whose numbers are in ascending or descending order, and switch the block around. For example, 916532748 may be changed to 913562748. Prove that in at most 12 moves, one can arrange the 9 cards so that their numbers are in ascending or descending order.

Solution

Let f(n) be the minimum number of moves needed to monotonize any permutation of n distinct numbers. Let us be given a permutation \pi of {1, 2, . . ., n}, and let k be the first element of \pi. In f(n−1) moves, we can transform \pi to either (k, 1, 2, . . . , k−1, k+1, . . . , n) or (k, n, n−1, . . ., k+ 1, k −1, . . . , 1). Now the former can be changed to (k, k −1, . . . , 2, 1, k + 1, . . . , n), which is then monotonized in the next move. Similarly, the latter also can be monotonized in two moves. It follows that f(n) \leqf(n−1)+2. Thus we shall be done if we show that f(5) \leq4. First we note that f(3) = 1. Consider a permutation of {1, 2, 3, 4}. If either 1 or 4 is the first or the last element, we need one move to monotonize the other three elements, and at most one more to monotonize the whole per- mutation. Of the remaining four permutations, (2, 1, 4, 3) and (3, 4, 1, 2) can also be monotonized in two moves. The permutations (2, 4, 1, 3) and (3, 1, 4, 2) require 3 moves, but by this we can choose whether to change them into (1, 2, 3, 4) or (4, 3, 2, 1). We now consider a permutation of {1, 2, 3, 4, 5}. If either 1 or 5 is in the first or last position, we can monotonize the rest in 3 moves, but in such a way that the whole permutation can be monotonized in the next move. If this is not the case, then either 1 or 5 is in the second or fourth position. Then we simply switch it to the outside in one move and continue as in the former case. Hence f(5) = 4, as desired.