Competition · AMC preparation · step 4 of 4

AMC 10 · 2022A · #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

Restate the condition

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

Count the case n = 1

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

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

Count the case n = 2

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

Count the case n = 3

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

Find the counting pattern

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

Apply it to n = 5

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.

  • Restate the condition
  • Count the case n = 1
  • Count the case n = 2
  • Count the case n = 3
  • Find the counting pattern
  • Apply it to n = 5

A parent dashboard for the family lives at sensimlab.com.