AMC 10 · 2022 · #24

Grade 6 counting

Archetype Branching State Enumeration └ Sub-archetype Constrained Sequence or Path Count

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

📏 Medium solution 💡 3 insights

Problem

Count the length-five strings whose entries are digits from 0 to 4 and which satisfy, for each value from one to four, that at least that many of the five digits are strictly less than it.

Pick an answer.

(A)

500

(B)

625

(C)

1089

(D)

1199

(E)

1296

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 on the sorted string

Sorting simplifies the condition.

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

2STEP 2

Count length one

Count the shortest case.

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

3STEP 3

Count length two

Count the next length.

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

4STEP 4

Count length three

Count the third length.

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

5STEP 5

Read off the pattern

The counts follow a clean formula.

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

6STEP 6

Apply it at length five

At length five it gives 1296.

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 12 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.