LIVE by Po-Shen Loh标识

LIVE

中文

2022 AMC 12A 第 19 题

先试着解答 2022 AMC 12A 第 19 题，然后核对你的答案与精心整理的解答，解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2022 AMC 12A 解答，或核对答案。

所有题目均经美国数学协会（MAA）官方合法授权使用。

19.

假设 1313 张编号为 11，22，33，…\ldots，1313 的卡片排成一行。任务是按数字递增顺序拿起它们，并反复从左到右扫描。在下面的例子中，第一次扫描拿起卡片 11，22，33，第二次扫描拿起 44 和 55，第三次扫描拿起 66，第四次扫描拿起 77，88，99，1010，第五次扫描拿起 1111，1212，1313。在 13!13! 种卡片排列中，有多少种会使这 1313 张卡片恰好在两次扫描中被拿起？

Suppose that 1313 cards numbered 1,1, 2,2, 3,3, …,\ldots, 1313 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,1, 2,2, 33 are picked up on the first pass, 44 and 55 on the second pass, 66 on the third pass, 7,7, 8,8, 9,9, 1010 on the fourth pass, and 11,11, 12,12, 1313 on the fifth pass. For how many of the 13!13! possible orderings of the cards will the 1313 cards be picked up in exactly two passes?

40824082

40954095

40964096

81788178

81918191

答案：D
知识点：排列找规律
难度评级：2010
小提示：

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

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

大提示：

两次扫描意味着位置序列 pos(1),…,pos(13)\text{pos}(1),\ldots,\text{pos}(13) 恰好有一个下降

Two passes means the sequence of positions pos(1),…,pos(13)\text{pos}(1),\ldots,\text{pos}(13) has exactly one descent

解答：

设 pos(k)\text{pos}(k) 为卡片 kk 的位置。正好在 pos(k+1)<pos(k)\text{pos}(k+1)\lt\text{pos}(k) 时需要开始新一轮扫描，因此扫描次数等于序列 pos(1),pos(2),…,pos(13)\text{pos}(1),\text{pos}(2),\ldots,\text{pos}(13) 的下降数加一。

要构造至多有一个下降的排列，只需选出排在可能的下降之前的那些元素，并把两块都按递增顺序写出。这样的子集共有 2132^{13} 个。其中 1414 个初始段 ∅,{1},…,{1,…,13}\varnothing,\{1\},\ldots,\{1,\ldots,13\} 不产生下降；其余每个子集都恰好给出一个含一个下降的排列。因此总数为 213−14=81782^{13}-14=8178。

因此，正确答案是 D。

Let pos(k)\text{pos}(k) be the position of card k.k. A fresh pass is needed exactly when pos(k+1)<pos(k),\text{pos}(k+1)\lt\text{pos}(k), so the number of passes is one more than the number of descents in the sequence pos(1),pos(2),…,pos(13).\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 2132^{13} subsets. The 1414 initial segments ∅,{1},…,{1,…,13}\varnothing,\{1\},\ldots,\{1,\ldots,13\} produce no descent; every other subset produces a unique permutation with one descent. Hence the count is 213−14=8178.2^{13}-14=8178.

Thus, the correct answer is D.

第 18 题#18
完整试卷
第 20 题#20

其他年份的第 19 题

1950 AMC 12 · 1951 AMC 12 · 1952 AMC 12 · 1953 AMC 12 · 1954 AMC 12 · 1955 AMC 12 · 1956 AMC 12 · 1957 AMC 12 · 1958 AMC 12 · 1959 AMC 12 · 1960 AMC 12 · 1961 AMC 12 · 1962 AMC 12 · 1963 AMC 12 · 1964 AMC 12 · 1965 AMC 12 · 1966 AMC 12 · 1967 AMC 12 · 1968 AMC 12 · 1969 AMC 12 · 1970 AMC 12 · 1971 AMC 12 · 1972 AMC 12 · 1973 AMC 12 · 1974 AMC 12 · 1975 AMC 12 · 1976 AMC 12 · 1977 AMC 12 · 1978 AMC 12 · 1979 AMC 12 · 1980 AMC 12 · 1981 AMC 12 · 1982 AMC 12 · 1983 AMC 12 · 1984 AMC 12 · 1985 AMC 12 · 1986 AMC 12 · 1987 AMC 12 · 1988 AMC 12 · 1989 AMC 12 · 1990 AMC 12 · 1991 AMC 12 · 1992 AMC 12 · 1993 AMC 12 · 1994 AMC 12 · 1995 AMC 12 · 1996 AMC 12 · 1997 AMC 12 · 1998 AMC 12 · 1999 AMC 12 · 2000 AMC 12 · 2001 AMC 12 · 2002 AMC 12A · 2002 AMC 12B · 2003 AMC 12A · 2003 AMC 12B · 2004 AMC 12A · 2004 AMC 12B · 2005 AMC 12A · 2005 AMC 12B · 2006 AMC 12A · 2006 AMC 12B · 2007 AMC 12A · 2007 AMC 12B · 2008 AMC 12A · 2008 AMC 12B · 2009 AMC 12A · 2009 AMC 12B · 2010 AMC 12A · 2010 AMC 12B · 2011 AMC 12A · 2011 AMC 12B · 2012 AMC 12A · 2012 AMC 12B · 2013 AMC 12A · 2013 AMC 12B · 2014 AMC 12A · 2014 AMC 12B · 2015 AMC 12A · 2015 AMC 12B · 2016 AMC 12A · 2016 AMC 12B · 2017 AMC 12A · 2017 AMC 12B · 2018 AMC 12A · 2018 AMC 12B · 2019 AMC 12A · 2019 AMC 12B · 2020 AMC 12A · 2020 AMC 12B · 2021 AMC 12A Spring · 2021 AMC 12B Spring · 2021 AMC 12A Fall · 2021 AMC 12B Fall · 2022 AMC 12B · 2023 AMC 12A · 2023 AMC 12B · 2024 AMC 12A · 2024 AMC 12B · 2025 AMC 12A · 2025 AMC 12B