2022 AMC 10A Problem 24

There are $5^5 = 3125$ strings in all. It is easier to count the strings that fail, sorted by the first condition they break.

Step 1: small good strings we will need. Call a string "good" if it passes all its conditions.
- Length $2$, digits $0, 1$, needing at least one digit less than $1$ (a $0$): $00, 01, 10$. That is $3$ strings.
- Length $3$, digits $0, 1, 2$, needing at least one $0$ and at least two digits less than $2$. Out of $27$ strings, $2^3 = 8$ have no $0$, and $3$ have exactly one $0$ with two $2$s ($022, 202, 220$). So $27 - 8 - 3 = 16$ are good.

Step 2: count the bad strings of length 5.

• First failure at $j = 1$: no digit is $0$. Each digit is one of $1, 2, 3, 4$: $4^5 = 1024$ strings.
• First failure at $j = 2$: there is a $0$, but at most one digit less than $2$. So there is exactly one $0$, no $1$s, and the other four digits are $2, 3$ or $4$. Place the $0$ in $5$ ways; the rest give $3^4 = 81$. Total $5 \times 81 = 405$.
• First failure at $j = 3$: at least two digits are less than $2$, but at most two are less than $3$. So exactly two digits are small (both $0$ or $1$), and they must include a $0$: they form one of the $3$ good pairs from Step 1. The other three digits are $3$ or $4$. Choose the two spots in $\binom52 = 10$ ways: $10 \times 3 \times 2^3 = 240$.
• First failure at $j = 4$: at least three digits are less than $3$, but at most three are less than $4$. So exactly three digits are small (each $0$, $1$ or $2$), and they must pass the earlier conditions: they form one of the $16$ good strings of length $3$. The other two digits must be $4$. Choose the three spots in $\binom53 = 10$ ways: $10 \times 16 \times 1 = 160$.

Each bad string has exactly one first failure, so nothing is counted twice. Bad strings: $1024 + 405 + 240 + 160 = 1829$.

Step 3: subtract. Good strings: $3125 - 1829 = 1296$.

The answer is $\boxed{\textbf{(E)}\ 1296}$.

The conditions build on one another, so a failing string has a first failure, and at that moment it splits cleanly into a shorter good string of small digits plus a block of large digits. That is why counting the failures works and why it reuses the counts for shorter strings. The counts for lengths $1$ to $5$ are $1, 3, 16, 125, 1296$, which are $2^0, 3^1, 4^2, 5^3, 6^4$, a pattern worth remembering.

Under time pressure, find the small cases and guess the pattern. Length $1$ (digit $0$ only): $1$ string. Length $2$: $3$ strings. Length $3$: $16$ strings (Step 1 above). The numbers $1, 3, 16$ are $2^0, 3^1, 4^2$, which suggests length $5$ gives $6^4 = 1296$, and that is one of the choices. Length $4$ can be checked the same way as Step 2: $256 - (81 + 32 + 18) = 125 = 5^3$, which supports the pattern.

Call a string of length $n$ over the digits $0, \dots, n-1$ good if for every $j = 1, \dots, n-1$ at least $j$ of its digits are less than $j$. Let $G_n$ be the number of good strings, with $G_0 = 1$ (the empty string). We want $G_5$.

Count the bad strings by their smallest failing $j$. Condition $j-1$ holds (at least $j-1$ digits below $j-1$) while condition $j$ fails (at most $j-1$ digits below $j$). Digits below $j-1$ are also below $j$, so exactly $j-1$ digits are below $j$, and all of them are actually below $j-1$. Among themselves these $j-1$ digits satisfy conditions $1, \dots, j-2$, so they form a good string of length $j-1$. The other $n-j+1$ digits are each at least $j$, chosen from the $n-j$ values $j, \dots, n-1$. Choosing the positions of the small digits,
$$\text{bad}_n = \sum_{j=1}^{n-1} \binom{n}{j-1}\, G_{j-1}\, (n-j)^{\,n-j+1}, \qquad G_n = n^n - \text{bad}_n.$$
(The case $j = n$ never fails.) Compute:

• $G_1 = 1$.
• $G_2 = 4 - \binom{2}{0} \cdot 1 \cdot 1^2 = 3$.
• $G_3 = 27 - \left(1 \cdot 1 \cdot 2^3 + \binom{3}{1} \cdot 1 \cdot 1^2\right) = 27 - 11 = 16$.
• $G_4 = 256 - \left(3^4 + \binom{4}{1} \cdot 1 \cdot 2^3 + \binom{4}{2} \cdot 3 \cdot 1^2\right) = 256 - 131 = 125$.
• $G_5 = 3125 - \left(4^5 + \binom{5}{1} \cdot 1 \cdot 3^4 + \binom{5}{2} \cdot 3 \cdot 2^3 + \binom{5}{3} \cdot 16 \cdot 1^2\right) = 3125 - (1024 + 405 + 240 + 160) = 1296$.

The answer is $\boxed{\textbf{(E)}\ 1296}$.