AMC 10 · 2022 · #24

Grade 6 arithmetic

combinations-basicsystematic-enumerationpattern-recognition easier-related-problempattern-recognitionsystematic-enumeration ↑ Prerequisites: combinations-basic

📏 Medium solution 💡 3 insights

Problem

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

$\textbf{(A) }500\qquad\textbf{(B) }625\qquad\textbf{(C) }1089\qquad\textbf{(D) }1199\qquad\textbf{(E) }1296$

Pick an answer.

(A)

500

(B)

625

(C)

1089

(D)

1199

(E)

1296

View mode:

Toolkit + CCSS Solution

Understand

Restated: Count length-$5$ strings $d_1 d_2 d_3 d_4 d_5$ where each $d_i \in \{0, 1, 2, 3, 4\}$ and, for each $j \in \{1, 2, 3, 4\}$, at least $j$ of the five digits are strictly less than $j$.

Givens: Digits drawn from $\{0, 1, 2, 3, 4\}$, string length $5$; For each $j \in \{1, 2, 3, 4\}$: at least $j$ digits are $< j$; Example $02214$ satisfies; $23404$ does not (only $1$ digit $< 2$); Answer choices: (A) $500$, (B) $625$, (C) $1089$, (D) $1199$, (E) $1296$

Unknowns: The number of valid strings

Understand

Restated: Count length-$5$ strings $d_1 d_2 d_3 d_4 d_5$ where each $d_i \in \{0, 1, 2, 3, 4\}$ and, for each $j \in \{1, 2, 3, 4\}$, at least $j$ of the five digits are strictly less than $j$.

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #2 Make a Systematic List, #3 Eliminate Possibilities

The full problem (length $5$, alphabet $\{0, \ldots, 4\}$) has $3125$ strings to filter — too many to list by hand. Tool #9 (Easier Problem): try the same kind of problem with length $n$ and alphabet $\{0, \ldots, n-1\}$ for $n = 1, 2, 3$. Tool #2 (Systematic List) does the small cases by hand. Tool #5 (Pattern): the counts $1, 3, 16$ fit $(n+1)^{n-1}$ exactly — these are the famous \emph{parking functions}. For $n = 5$ this gives $6^4 = 1296$, choice (E). Tool #3 (Eliminate) cross-checks against the answer list and rules out (C) $1089 = 33^2$ and (D) $1199$ which would not arise from a clean exponent pattern.

Execute — Answer: E

#9 Solve an Easier Related Problem 6.EE.B.8 Step 1

Restate the condition cleanly.
Sort the five digits as $d_{(1)} \le \ldots \le d_{(5)}$.
"At least $j$ digits are $< j$" is the same as "the $j$-th smallest digit is $< j$", i.e.
$d_{(j)} < j$.
So the condition is exactly $d_{(1)} = 0$, $d_{(2)} \le 1$, $d_{(3)} \le 2$, $d_{(4)} \le 3$ (the digit $d_{(5)}$ can be anything in $\{0, 1, 2, 3, 4\}$).

$$d_{(j)} < j \text{ for } j = 1, 2, 3, 4$$

💡 Grade 6 — the condition on the sorted sequence is the same as the original "count" condition.

#9 Solve an Easier Related Problem K.OA.A.5 Step 2

Tiny case $n = 1$.
Strings of length $1$ from $\{0\}$ with at least $1$ digit $< 1$.
Only string: $0$.
Count $= 1 = 2^0$.

$$n = 1: \text{count} = 1 = (1+1)^{1-1}$$

💡 Kindergarten — count to $1$.

#2 Make a Systematic List 2.OA.C.4 Step 3

Tiny case $n = 2$.
Strings of length $2$ from $\{0, 1\}$ with at least $1$ digit $< 1$ (and at least $2$ digits $< 2$, vacuously true).
Need at least one $0$.
Strings: $00, 01, 10$.
Count $= 3 = 3^1$.

$$n = 2: \text{count} = 3 = (2+1)^{2-1}$$

💡 Grade 2 — list all $4$ length-$2$ binary strings and exclude $11$.

#2 Make a Systematic List 4.OA.B.4 Step 4

Tiny case $n = 3$.
Strings of length $3$ from $\{0, 1, 2\}$ needing at least one $0$ AND at least two digits in $\{0, 1\}$.
Casework on the multiset: $\{0, 0, 0\}$: $1$ string.
$\{0, 0, x\}$ with $x \in \{1, 2\}$: $2 \cdot \binom{3}{1} = 6$ strings.
$\{0, 1, x\}$ with $x \in \{1, 2\}$: $\{0, 1, 1\}$ has $3$ arrangements, $\{0, 1, 2\}$ has $6$, total $9$.
Sum $= 1 + 6 + 9 = 16 = 4^2$.

$$n = 3: \text{count} = 16 = (3+1)^{3-1}$$

💡 Grade 4 — case-by-case enumeration of valid digit multisets and their arrangements.

#5 Look for a Pattern 4.OA.C.5 Step 5

Spot the pattern.
$1, 3, 16, \ldots$ matches $(n+1)^{n-1}$: $2^0 = 1$, $3^1 = 3$, $4^2 = 16$.
(These are the classical parking-function counts — for a length-$n$ string of digits in $\{0, \ldots, n-1\}$, the condition $d_{(j)} < j$ for all $j$ is exactly the parking-function definition; the closed form $(n+1)^{n-1}$ is a famous result due to Cayley.)

$$\text{count}(n) = (n+1)^{n-1}$$

💡 Grade 4 — three data points already pin down the exponential pattern $(n+1)^{n-1}$.

#5 Look for a Pattern 6.EE.A.1 Step 6

Apply to $n = 5$.
Count $= (5+1)^{5-1} = 6^4 = 36 \cdot 36 = 1296$.
This is choice (E).

$$6^4 = 1296 \;\Rightarrow\; \textbf{(E)}$$

💡 Grade 6 — plug $n = 5$ into the pattern.

[1] #9 6.EE.B.8 Restate the condition cleanly. Sort the five digits as $d_{(1)} \le \ldots \le d

[2] #9 K.OA.A.5 Tiny case $n = 1$. Strings of length $1$ from $\{0\}$ with at least $1$ digit $<

[3] #2 2.OA.C.4 Tiny case $n = 2$. Strings of length $2$ from $\{0, 1\}$ with at least $1$ digit

[4] #2 4.OA.B.4 Tiny case $n = 3$. Strings of length $3$ from $\{0, 1, 2\}$ needing at least one

[5] #5 4.OA.C.5 Spot the pattern. $1, 3, 16, \ldots$ matches $(n+1)^{n-1}$: $2^0 = 1$, $3^1 = 3$

[6] #5 6.EE.A.1 Apply to $n = 5$. Count $= (5+1)^{5-1} = 6^4 = 36 \cdot 36 = 1296$. This is choi

Review

Reasonableness: Sanity. Total strings without the condition: $5^5 = 3125$. The answer $1296$ is about $41\%$ of that — plausible because the condition is moderately restrictive (most strings starting with all small digits will satisfy it; only strings heavy on $3$'s and $4$'s violate it). Also $1296 = 6^4$ has the clean exponential form expected for a parking-function-like count. The small cases $1, 3, 16$ verified by listing match $(n+1)^{n-1}$ exactly, so the formula is trustworthy at $n = 5$.

Alternative: Tool #2 (Direct enumeration / Casework) on $n = 5$: split by the number of distinct digits in the multiset ($1, 2, 3, 4, 5$ distinct), check the sorted-condition on each multiset, count permutations. The reference solution does this and gets $1 + 75 + 500 + 600 + 120 = 1296$. Tool #3 (Eliminate): the only choice equal to $6^4$ is (E); (B) $625 = 5^4$ is the trap if a student writes $5^{n-1}$ instead of $(n+1)^{n-1}$, and (A) $500$ matches one sub-case of the casework — both ruled out by the small-case pattern.

CCSS standards used (min grade 6)

K.OA.A.5 Fluently add and subtract within $5$ (Counting the unique length-$1$ string $0$.)
2.OA.C.4 Use addition to find the total number of objects arranged in rectangular arrays (Enumerating the $4$ length-$2$ binary strings and removing the $1$ violator.)
4.OA.B.4 Find all factor pairs for a whole number; recognize whether a whole number is a multiple of a given one-digit number (Casework on the length-$3$ multisets and counting their arrangements.)
4.OA.C.5 Generate a number or shape pattern that follows a given rule (Reading the data points $1, 3, 16$ as the pattern $(n+1)^{n-1}$.)
6.EE.A.1 Write and evaluate numerical expressions involving whole-number exponents (Evaluating $6^4 = 1296$ at $n = 5$.)
6.EE.B.8 Write an inequality of the form $x > c$ or $x < c$ to represent a constraint (Rewriting the original condition as inequalities $d_{(j)} < j$ on the sorted digits.)

⭐ This AMC 10 problem only needs Grade 6 exponents you already know — sort the digits, see that the rule becomes $d_{(j)} < j$, try $n = 1, 2, 3$ by hand (counts $1, 3, 16$), spot the pattern $(n+1)^{n-1}$, and plug $n = 5$ to get $6^4 = 1296$.