Question

设 $(a_1,a_2,\ldots,a_{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

解答：

从 $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 题