2012 AMC 12B 第 18 题

Question

设

(a_1, a_2, \ldots, a_{10})

是前

10

个正整数的一个排列，并且对每个

2 \le i \le 10

，

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 \le 10

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

知识点：双射组合

难度评级：1990

小提示：

大于或等于

a_1

的数必须按递增顺序出现，小于

a_1

的数必须按递减顺序出现

The numbers greater than or equal to

a_1

must appear in increasing order, and those less than

a_1

in decreasing order

大提示：

选择哪些位置放较小的数即可确定整个排列，得到

\sum_k \binom{9}{k}

Choosing which positions hold the small numbers determines the list, giving

\sum_k \binom{9}{k}

解答：

一旦固定

a_1=k

，数

k,k+1,\ldots,10

必须从左到右按递增顺序出现，而数

1,\ldots,k-1

必须从右到左按递增顺序出现（这样每个新出现的较小数都有它的后继已经放好）。

对每个

k

，只需选择第一个位置之后的

9

个位置中哪些放小于

k

的数，因此有

\binom{9}{k-1}

个排列。

求和得

\begin{aligned} \sum_{k=1}^{10}\binom{9}{k-1} &= \sum_{j=0}^{9}\binom{9}{j} \\ &= 2^9=512 \end{aligned}\text{。}

因此正确答案是 B。

Once

a_1=k

is fixed, the numbers

k,k+1,\ldots,10

must appear left to right in increasing order, and the numbers

1,\ldots,k-1

must appear from right to left in increasing order (so each new small number has its successor already placed).

For each

k,

the list is determined by choosing which of the

9

positions after the first hold the numbers below

k,

giving

\binom{9}{k-1}

lists.

Summing,

\begin{aligned} \sum_{k=1}^{10}\binom{9}{k-1} &= \sum_{j=0}^{9}\binom{9}{j} \\ &= 2^9=512. \end{aligned}

Thus, the correct answer is B.

2012 AMC 12B 第 18 题

答案：B

难度评级：1990

小提示：

大提示：

解答：

其他年份的第 18 题