A small fish is holding 17 cards, labeled 1 through 17, which he shuffles into a random order. Then, he notices that although the cards are not currently sorted in ascending order, he can sort them into ascending order by removing one card and putting it back in a different position (at the beginning, between some two cards, or at the end). In how many possible orders could his cards currently be?
Solution
Instead of looking at moves which put the cards in order, we start with the cards in order and consider possible starting positions by backtracking one move: each of 17 cards can be moved to 16 new places. But moving card between card and card is equivalent to moving card between card and card . We note that these are the only possible pairs of moves which produce the same result, so we have double counted 16 moves. Thus, we have a total of possible initial positions.
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.