2022 AMC 10A 第 22 题

Question

有

13

张编号为

1

，

2

，

3

，

\cdots

，

13

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

1

，

2

，

3

，第二次拿起

4

、

5

，第三次拿起

6

，第四次拿起

7

，

8

，

9

，

10

，第五次拿起

11

，

12

，

13

。在所有

13!

种排列中，有多少种排列会使

13

张卡片恰好用两次扫描拿完？

Suppose that

13

cards numbered

1,

2,

3,

\cdots,

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

知识点：组合补集计数

难度评级：1660

小提示：

第一次扫描取走的卡片必须构成一个递增子序列

The cards picked up on the first pass must occupy an increasing subsequence

大提示：

选定第一次扫描取走的卡片所占的位置，并排除只需一次扫描就取完的排列

Choose the positions of the first-pass cards and exclude one-pass arrangements

解答：

设第一次扫描拿到

n

张卡片，其中

1 \leq n \leq 12

。

选择这

n

张卡片所占的位置后，剩余卡片的位置也被确定，因为两组卡片都必须按递增顺序排列。

\binom{13}{n}

种方法选择这

n

张卡片的位置；但若这

n

张卡片恰好位于最前面，则所有卡片都会在第一次扫描中拿完。

因此对固定的

n

，共有

\binom{13}{n} - 1

种排列。

对

1\le n\le12

求和，得到

\begin{gathered} \sum_{n=1}^{12}\left(\binom{13}{n}-1\right) \\ = (2^{13}-2)-12 \\ = 8178 \end{gathered}\text{。}

所以正确答案是 D。

Let

n

be the number of cards picked up on the first pass, where

1 \leq n \leq 12.

If we choose the spaces that the

n

cards occupy, the positions of the remaining cards are determined since they must be placed in order.

There are

\binom{13}{n}

ways to choose where the

n

cards go, but if the

n

cards are placed at the very beginning, then all the cards will be picked up on the first pass.

Therefore, for a given

n

there are

\binom{13}{n} - 1

ways to arrange the cards.

Summing over

1\le n\le12,

we get

\begin{gathered} \sum_{n=1}^{12}\left(\binom{13}{n}-1\right) \\ = (2^{13}-2)-12 \\ = 8178. \end{gathered}

Thus, D is the correct answer.

2022 AMC 10A 第 22 题

答案：D

难度评级：1660

小提示：

大提示：

解答：

其他年份的第 22 题