2022 AMC 10A Problem 24

P21-25~12 minPrint

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

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

Show solution without answering

Key insight

Count the bad strings by the first condition they break. At that point the string splits into a smaller good string of low digits plus a block of high digits.

Solution

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

Why this works

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.

Alternative approach

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.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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

Review in the AoPS books

Intermediate Counting & Probability, Chapter 10: Recursion (§10.2, §10.3)
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.3)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)