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 rando m order. Then, he notices that although the cards are not currently sorted in ascending order, he can s ort 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 cur rently 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 theminto 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 cardsin order and consider possible starting positions by backtracking one move: each of 17 cards can bemoved to 16 new places. But moving card k between card k + 1 and card k + 2 is equivalent tomoving card k + 1 between card k − 1 and card k . We note that these are the only possible pairs ofmoves 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.