HMMT 十一月 2011 · 冲刺赛 · 第 16 题

HMMT November 2011 — Guts Round — Problem 16

[ 10 ] 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?

解析

[ 10 ] 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? Answer: 256 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 × 16 − 16 = 256 possible initial positions.