AMC 10 · 2022 · #24

Grade 6 arithmetic

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

📏 Medium solution 💡 3 insights

Problem

Count length-5 strings d₁ d₂ d₃ d₄ d₅ where each d_i ∈ {0, 1, 2, 3, 4} and, for each j ∈ {1, 2, 3, 4}, at least j of the five digits are strictly less than j.

Pick an answer.

(A)

500

(B)

625

(C)

1089

(D)

1199

(E)

1296

AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Solve an Easier Related Problem

The full problem (length 5, alphabet {0, …, 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, …, 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)ⁿ⁻¹ exactly — these are the famous parking functions. For n = 5 this gives 6⁴ = 1296, choice (E). Tool #3 (Eliminate) cross-checks against the answer list and rules out (C) 1089 = 33² and (D) 1199 which would not arise from a clean exponent pattern.

1STEP 1

Sort the digits d_(1) ≤ … ≤ d_(5); then "at least j digits below j" is exactly d_(j) ＜ j for j = 1, 2, 3, 4 (d_(5) is free).

d_(j) ＜ j for j = 1, 2, 3, 4

2STEP 2

Length 1 from {0}: only the string 0 works, so the count is 1 = 2⁰.

n = 1: count = 1 = (1+1)¹⁻¹

3STEP 3

Length 2 from {0, 1}: need at least one 0, giving 00, 01, 10 — the count is 3 = 3¹.

n = 2: count = 3 = (2+1)²⁻¹

4STEP 4

Length 3 from {0, 1, 2}: casework on the multiset gives 1 + 6 + 9 = 16 = 4² strings.

n = 3: count = 16 = (3+1)³⁻¹

5STEP 5

The counts 1, 3, 16 fit (n+1)ⁿ⁻¹ exactly (2⁰, 3¹, 4²) — these are the classic parking-function counts.

count(n) = (n+1)ⁿ⁻¹

6STEP 6

Put n = 5 into the formula: (5+1)⁵⁻¹ = 6⁴ = 1296, choice (E).

6⁴ = 1296 → (E)

Answer

1296

Sanity. Total strings without the condition: 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⁴ has the clean exponential form expected for a parking-function-like count. The small cases 1, 3, 16 verified by listing match (n+1)ⁿ⁻¹ exactly, so the formula is trustworthy at n = 5.

💡Key takeaway

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)ⁿ⁻¹, and plug n = 5 to get 6⁴ = 1296.