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$

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

Counting the ordered strings of digits from $\{0,1,2,3,4\}$ whose sorted values obey these bounds gives $1296.$

Thus, the correct answer is E.

2022 AMC 12A Problem 24

Solution:

Problem 24 in Other Years