Question

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$

Answer: E

Concepts:arrangements with restrictions casework

Difficulty rating: 2380

Small Hint:

“At least $j$ digits are less than $j$ ” means the $j$ th smallest digit is at most $j-1$

Big Hint:

These are parking functions of length $5;$ use the circular-parking count with $6$ spaces

Solution:

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 Problem 24

Answer: E

Difficulty rating: 2380

Small Hint:

Big Hint:

Solution:

Problem 24 in Other Years