2022 AMC 12A 第 19 题

Question

假设

13

张编号为

1

，

2

，

3

，

\ldots

，

13

的卡片排成一行。任务是按数字递增顺序拿起它们，并反复从左到右扫描。在下面的例子中，第一次扫描拿起卡片

1

，

2

，

3

，第二次扫描拿起

4

和

5

，第三次扫描拿起

6

，第四次扫描拿起

7

，

8

，

9

，

10

，第五次扫描拿起

11

，

12

，

13

。在

13!

种卡片排列中，有多少种会使这

13

张卡片恰好在两次扫描中被拿起？

Suppose that

13

cards numbered

1,

2,

3,

\ldots,

13

are arranged in a row. The task is to pick them up in numerically increasing order, working repeatedly from left to right. In the example below, cards

1,

2,

3

are picked up on the first pass,

4

and

5

on the second pass,

6

on the third pass,

7,

8,

9,

10

on the fourth pass, and

11,

12,

13

on the fifth pass. For how many of the

13!

possible orderings of the cards will the

13

cards be picked up in exactly two passes?

4082

4095

4096

8178

8191

答案：D

知识点：排列找规律

难度评级：2010

小提示：

当下一个要拿的数位于前一个数的左边时，就必须开始新一轮扫描

A new pass begins exactly when the next number to pick up lies to the left of the previous one

大提示：

两次扫描意味着位置序列

\text{pos}(1),\ldots,\text{pos}(13)

恰好有一个下降

Two passes means the sequence of positions

\text{pos}(1),\ldots,\text{pos}(13)

has exactly one descent

解答：

设

\text{pos}(k)

为卡片

k

的位置。正好在

\text{pos}(k+1)\lt\text{pos}(k)

时需要开始新一轮扫描，因此扫描次数等于序列

\text{pos}(1),\text{pos}(2),\ldots,\text{pos}(13)

的下降数加一。

要构造至多有一个下降的排列，只需选出排在可能的下降之前的那些元素，并把两块都按递增顺序写出。这样的子集共有

2^{13}

个。其中

14

个初始段

\varnothing,\{1\},\ldots,\{1,\ldots,13\}

不产生下降；其余每个子集都恰好给出一个含一个下降的排列。因此总数为

2^{13}-14=8178

。

因此，正确答案是 D。

Let

\text{pos}(k)

be the position of card

k.

A fresh pass is needed exactly when

\text{pos}(k+1)\lt\text{pos}(k),

so the number of passes is one more than the number of descents in the sequence

\text{pos}(1),\text{pos}(2),\ldots,\text{pos}(13).

To build a permutation with at most one descent, choose the entries before the possible descent and write both chosen blocks in increasing order. There are

2^{13}

subsets. The

14

initial segments

\varnothing,\{1\},\ldots,\{1,\ldots,13\}

produce no descent; every other subset produces a unique permutation with one descent. Hence the count is

2^{13}-14=8178.

Thus, the correct answer is D.

2022 AMC 12A 第 19 题

答案：D

难度评级：2010

小提示：

大提示：

解答：

其他年份的第 19 题