2022 AMC 12A 第 24 题

Question

用数字

0

，

1

，

2

，

3

，

4

组成长度为

5

的字符串。有多少个这样的字符串满足：对每个

j\in\{1,2,3,4\}

，至少有

j

个数字小于

j

？（例如，

02214

满足条件，因为它含有至少

1

个小于

1

的数字，至少

2

个小于

2

的数字，至少

3

个小于

3

的数字，且至少

4

个小于

4

的数字。字符串

23404

不满足条件，因为它不含至少

2

个小于

2

的数字。）

How many strings of length

5

formed from the digits

0,

1,

2,

3,

4

are there such that for each

j\in\{1,2,3,4\},

at least

j

of the digits are less than

j?

(For example,

02214

satisfies the condition because it contains at least

1

digit less than

1,

at least

2

digits less than

2,

at least

3

digits less than

3,

and at least

4

digits less than

4.

The string

23404

does not satisfy the condition because it does not contain at least

2

digits less than

2.

)

500

625

1089

1199

1296

答案：E

知识点：有限制的排列分类讨论

难度评级：2380

小提示：

“至少有

j

个数字小于

j

” 意味着第

j

小的数字至多为

j-1

。

“At least

j

digits are less than

j

” means the

j

th smallest digit is at most

j-1

大提示：

这些正是长度为

5

的停车函数；使用

6

个车位的圆形停车计数

These are parking functions of length

5;

use the circular-parking count with

6

spaces

解答：

将五个数字排序为

d_{(1)}\le d_{(2)}\le\cdots\le d_{(5)}

。条件“至少有

j

个数字小于

j

”等价于对

j=1,2,3,4

，有

d_{(j)}\le j-1

，即

d_{(1)}=0,\ d_{(2)}\le1

，

\ d_{(3)}\le2,\ d_{(4)}\le3

（而

d_{(5)}\le4

自动成立）。

这些字符串恰好是长度为

5

的停车函数。为计数，将

6

个停车位排成圆形，让

5

辆有标号的汽车任意选择首选车位。每辆车向前行驶到第一个空位。在

6^5

个偏好字符串中，同时旋转所有偏好会使唯一的空位依次经过全部

6

个位置。因此，恰有

\frac{6^5}{6}=6^4=1296

个字符串使指定车位为空。将这个车位选作额外的第六个车位，恰好得到上述排序不等式。

因此，正确答案是 E。

Sort the five digits as

d_{(1)}\le d_{(2)}\le\cdots\le d_{(5)}.

The requirement “at least

j

digits less than

j

” is equivalent to

d_{(j)}\le j-1

for

j=1,2,3,4,

i.e.

d_{(1)}=0,\ d_{(2)}\le1,

\ d_{(3)}\le2,\ d_{(4)}\le3

(with

d_{(5)}\le4

automatic).

These strings are exactly the parking functions of length

5.

To count them, arrange

6

parking spaces in a circle and let

5

labeled cars choose arbitrary preferred spaces. Each car moves forward to the first open space. Among the

6^5

preference strings, rotating all preferences cycles the unique empty space through all

6

positions. Therefore exactly

\frac{6^5}{6}=6^4=1296

strings leave a specified space empty. Choosing that space as the extra sixth space gives precisely the sorted inequalities above.

Thus, the correct answer is E.

2022 AMC 12A 第 24 题

答案：E

难度评级：2380

小提示：

大提示：

解答：

其他年份的第 24 题