AMC 10 · 2025 · #23

Grade 12 counting
Archetype Branching State Enumeration └ Sub-archetype Constrained Sequence or Path Count
combinations-basicbinomial-theoremdigit-constraintsfundamental-counting-principle pattern-recognitionidentify-subproblems ↑ Prerequisites: combinations-basicbinomial-theorem
📏 Medium solution 💡 3 insights
Problem
A positive integer is called fair when its digits are all different, none of them is 0, and no digit sits between two neighbors that are both larger than it. Count how many fair positive integers exist.

Pick an answer.

(A)
511
(B)
2584
(C)
9841
(D)
17711
(E)
19682
How to solve
Strategy Make a Systematic List

The rule 'no digit trapped below two larger neighbors' is hard to count directly, so I first translate it into a shape: what do the valid digit strings actually look like? Once I see they must climb to a single peak and come back down, counting splits into two clean subproblems. First I fix the set of digits used and count the mountain arrangements it allows, which turns out to be a simple power of two. Then I add those counts over every possible set of digits, and the binomial theorem folds the whole sum into one power of three. Grouping by which digits are used keeps the count organized and free of double counting.

1STEP 1

No valley means a mountain shape

All digits differ, so every step strictly rises or falls. Banning valleys (down-then-up) forces one climb to a single peak, then descends.

d₁ ＜ d₂ ＜ … ＜ d_peak ＞ … ＞ d_k
2STEP 2

Count the mountains from one chosen set

Fix k digits. The largest is forced to the peak; each other digit picks the rising or falling side, so each set gives 2^k-1.

2^k-1 fair numbers from each k-digit set
3STEP 3

Add over every set size

A k-digit set can be chosen C(9, k) ways, each giving 2^k-1 fair numbers; summing over k = 1..9 makes the total one clean sum.

total = Σ_k=1⁹ C(9, k) 2^k-1
4STEP 4

Collapse the sum with the binomial theorem

Pull out 12\frac{1}{2}: the binomial theorem gives Σ C(9,k)2^k = 3⁹ = 19683, so 39−12\frac{3⁹ - 1}{2} = 9841, choice (C).

1/2(Σ_k=0⁹C(9, k)2^k - 1) = (3⁹ - 1)/2 = 19682/2 = 9841
Answer
9841
The count 9841 is exactly half of the trap value 19682 = 3⁹ - 1, which is right: pinning the peak to the largest digit removes one binary choice and so divides the raw 2^k count by 2. A tiny case confirms the whole method. Using only digits from {1, 2, 3}, the formula predicts C(3,1)2⁰ + C(3,2)2¹ + C(3,3)2² = 3 + 6 + 4 = 13, and 33−12\frac{3³ - 1}{2} = 262\frac{26}{2} = 13 agrees. Listing by hand also gives 13: the singles 1, 2, 3; the pairs 12, 21, 13, 31, 23, 32; and the triples 123, 132, 231, 321 (while 213 is correctly excluded because its 1 sits between the larger 2 and 3).
💡Key takeaway

Turn a confusing rule into a shape: 'no digit trapped below two bigger ones' just means the number climbs to one peak and comes back down, and then you only pick a side for each digit.

  • No valley means a mountain shape
  • Count the mountains from one chosen set
  • Add over every set size
  • Collapse the sum with the binomial theorem

More like this

Same archetype — closest grade level first.