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

解答：

设 $\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 题