A group of people, no two of them are of the same height, are placed in random order in a line. They play a game as follows. At each step, a group of at most people swap places so that they are now arranged in increasing order of height. Everybody else stays put. Prove that it is always possible to arrange the whole group of people by height in at most steps.
Solution
At each step, choose the tallest and second tallest person not yet in their places, as well as the two people in the last two places which are not in the right order. By rearranging these, we get the tallest and second tallest persons in place. After steps we will be left with at most people not in place so we may need one more step.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.