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

$500$

$625$

$1089$

$1199$

$1296$

Solution:

Note that there must be at least one $0$ to satisfy the condition. We can proceed by casework on the number of distinct digits in the string.

$1$ digit

The only possible digit is just $0.$ This can be done in $1$ way.

$2$ digits

This gives us a total of $20 + 30 + 20 + 5 = 75$ strings.

$3$ digits

This gives us a total of $120 + 150 + 90 + 60 + 60$ $+ 20 = 500$ strings.

$4$ digits

This gives us a total of $10 \cdot \dfrac{5!}{2! \cdot 1! \cdot 1! \cdot 1!} = 600$ strings.

$5$ digits

This gives us $5! = 120$ strings.

All together, we have $1 + 75 + 500 + 600$ $+ 120 = 1296$ strings.

Thus, E is the correct answer.

2022 AMC 10A Problem 24

Solution:

Problem 24 in Other Years