HMMT-Nov 2011 guts, Problem 16

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 $k$ between card $k+1$ and card $k+2$ is equivalent to moving card $k+1$ between card $k-1$ and card $k$. 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 $17 \times 16-16=256$ possible initial positions. $\fbox{256}$.

Answer: 256