You are given 16 pieces of paper numbered in that order. You want to put them in the order switching only two adjacent pieces of paper at a time. What is the minimum number of switches necessary?
Solution
Piece 16 has to move to the back 15 times, piece 15 has to move to the back 14 times, ..., piece 2 has to move to the back 1 time, piece 1 has to move to the back 0 times. Since only one piece can move back in each switch, we must have at least switches.
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.