MathDB
IMO ShortList 1998, combinatorics theory problem 3

Source: IMO ShortList 1998, combinatorics theory problem 3

October 22, 2004
combinatoricspermutationIMO Shortlist

Problem Statement

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, 9 1 6 5 3‾\underline{6\ 5\ 3} 2 7 4 82\ 7\ 4\ 8 may be changed to 919 1 3 5 6‾\underline{3\ 5\ 6} 2 7 4 82\ 7\ 4\ 8. Prove that in at most 12 moves, one can arrange the 9 cards so that their numbers are in ascending or descending order.
Back to ProblemsView on AoPS