Printable

2022 AMC 10A Problem 24

2022 AMC 10A Problem 24AMC 10 Step by Step

Name: Date: September 13, 2026

Recursive Counting · difficulty 5 of 5 · about 12 min · position P21-25

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

A)
$500$
B)
$625$
C)
$1089$
D)
$1199$
E)
$1296$

Answer

Key insight

In a bad string, the smallest failing j has exactly j-1 digits below j-1 (a good string) and the rest at least j; recursing gives 1, 3, 16, 125, 1296.

Solution

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

Why this works

The condition is monotone in $j$ , so a failing string has a first failure, and at that point the string splits cleanly into a good short string of small digits and a block of unconstrained large digits. That split is what makes complementary counting recursive. These are the parking functions, and $G_n = (n+1)^{n-1}$ : $1, 3, 16, 125, 1296$ are $2^0, 3^1, 4^2, 5^3, 6^4$ .

Alternative approach

Under time pressure, compute the small cases directly: $G_1 = 1$ , $G_2 = 3$ (strings $00, 01, 10$ ), $G_3 = 16$ by a short list or the recursion. Spotting $1, 3, 16 = 2^0, 3^1, 4^2$ suggests $G_5 = 6^4 = 1296$ , which is the only choice of that form; one more step ( $G_4 = 125 = 5^3$ ) confirms the pattern.

The trap

Miscounting the free digits in the complement: each must be at least j, so there are 5 - j values for it, not 5 - j + 1 or 5.

Common mistakes

Miscounting the free digits in the complement: each must be at least j, so there are 5 - j values for it, not 5 - j + 1 or 5.
Counting only the $42$ sorted digit patterns (multisets) and forgetting to multiply each by its number of rearrangements.

Techniques

Count the complement and subtract from the total · Compute small cases, spot the pattern, generalize · Define states/recurrence and iterate