AMC12 2022 A

AMC12 2022 A · Q24

AMC12 2022 A · Q24. It mainly tests Basic counting (rules of product/sum), Counting & probability misc.

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 this 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$.)

由数字 $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$ 的数字。）

(A) 500 500

(B) 625 625

(D) 1199 1199

(E) 1296 1296

Answer

Correct choice: (E)

正确答案：（E）

Solution

For some $n$, let there be $n+1$ parking spaces counterclockwise in a circle. Consider a string of $n$ integers $c_1c_2 \ldots c_n$ each between $0$ and $n$, and let $n$ cars come into this circle so that the $i$th car tries to park at spot $c_i$, but if it is already taken then it instead keeps going counterclockwise and takes the next available spot. After this process, exactly one spot will remain empty. Then the strings of $n$ numbers between $0$ and $n-1$ that contain at least $k$ integers $<k$ for $1 \leq k \leq n$ are exactly the set of strings that leave spot $n$ empty. Also note for any string $c_1c_2 \ldots c_n$, we can add $1$ to each $c_i$ (mod $n+1$) to shift the empty spot counterclockwise, meaning for each string there exists exactly one $j$ with $0 \leq j \leq n$ so that $(c_1+j)(c_2+j) \ldots (c_n+j)$ leaves spot $n$ empty. This gives there are $\frac{(n+1)^{n}}{n+1} = (n+1)^{n-1}$ such strings. Plugging in $n = 5$ gives $\boxed{\textbf{(E) }1296}$ such strings.

对于某个 $n$，考虑逆时针有 $n+1$ 个停车位成圆形。考虑 $n$ 个整数 $c_1c_2 \ldots c_n$ 的字符串，每个介于 $0$ 和 $n$ 之间，让 $n$ 辆车进入这个圆，第 $i$ 辆车试图停在位置 $c_i$，但如果已被占用则继续逆时针走并停在下一个空位。经过此过程，正好一个空位剩余。则包含至少 $k$ 个整数 $<k$ 的 $n$ 个介于 $0$ 和 $n-1$ 之间的数字字符串恰好是使位置 $n$ 空着的字符串的集合。另注意对于任意字符串 $c_1c_2 \ldots c_n$，我们可以对每个 $c_i$ 加 $1$（模 $n+1$）来逆时针平移空位，意味着对于每个字符串存在唯一 $j$（$0 \leq j \leq n$）使得 $(c_1+j)(c_2+j) \ldots (c_n+j)$ 使位置 $n$ 空着。这给出此类字符串数为 $\frac{(n+1)^{n}}{n+1} = (n+1)^{n-1}$。代入 $n = 5$ 得 $\boxed{\textbf{(E) }1296}$ 个此类字符串。

Topics