Question

设 $(a_1,a_2,\ldots,a_{10})$ 是前 $10$ 个正整数的一个排列，并且对每个 $2\le i\le10$ ， $a_i + 1$ 或 $a_i-1$ 中至少有一个已经出现在 $a_i$ 前面。这样的排列有多少个？

Let $(a_1,a_2,\ldots,a_{10})$ be a list of the first $10$ positive integers such that for each $2\le i\le10$ either $a_i + 1$ or $a_i-1$ or both appear somewhere before $a_i$ in the list. How many such lists are there?

$\ 120$

$512$

$\ 1024$

$181{,}440$

$362{,}880$

答案：B

知识点：有限制的排列递推计数逆推法

难度评级：2060

小提示：

反向构造时，每一步移除当前剩余数中的最小值或最大值。

At each reverse step, remove either the smallest or largest remaining number

大提示：

直到最后一个数被迫确定之前，每一步都有 $2$ 种选择。

There are $2$ choices until the final number is forced

解答：

每个前缀 $a_1,a_2,\ldots,a_i$ 都必须构成一个连续整数区间，因为每个新加入的数必须比已出现的某个数大一或小一。特别地，完整集合就是区间 $[1,10]$ 。

反向阅读这个排列。每一步删去的项必须是当前区间的最小值或最大值；若删去内部的数，那么正向排列中该数前面就没有与它相邻的整数。反之，每一种依次删去端点的方式都能产生一个合格排列。对 $a_{10},a_9,\ldots,a_2$ 中的每一项都有两种选择，之后 $a_1$ 被唯一确定，所以总数为 $2^9=512$ 。

所以正确答案是 B。

Every prefix $a_1,a_2,\ldots,a_i$ must form an interval of consecutive integers: each new term is required to be one more or one less than a term already present. In particular, the full set is the interval $[1,10].$

Read the list backward. At each step, the term removed must be either the smallest or the largest integer in the current interval; removing an interior term would leave that term with no adjacent predecessor in the forward list. Conversely, every sequence of endpoint removals produces a valid list. There are two choices for each of $a_{10},a_9,\ldots,a_2,$ after which $a_1$ is forced. Hence there are $2^9=512$ lists.

Thus, the correct answer is B .

2012 AMC 10B 第 22 题

答案：B

难度评级：2060

小提示：

大提示：

解答：

其他年份的第 22 题