AMC 10 · 2023 · #8

Grade 11 counting
Archetype Casework by Position / Vertex Type └ Sub-archetype Count of Type
combinations-basicset-partitionbound-inequality-then-enumeratecasework identify-subproblemscaseworkbound-inequality-then-enumerate ↑ Prerequisites: combinations-basiccasework
📏 Medium solution 💡 3 insights
Problem
From the numbers zero through twelve, pick a nonempty collection. It counts only if the number of elements equals its smallest element. Find how many collections pass this test.

Pick an answer.

(A)
256
(B)
136
(C)
108
(D)
144
(E)
156
How to solve
Strategy Identify Subproblems

There are 2¹³ subsets in play, so checking them one at a time is hopeless by hand. The rule ties two features of B together — its size and its smallest element — and Tool #4 (Introduce a Variable) collapses those two into one letter k. Once k is named, Tool #7 (Identify Subproblems) does the real work: every subset has exactly one smallest element, so sorting the subsets by that value cuts the single hard count into a few small counts that overlap nowhere and miss nobody. Tool #14 (Extreme Principle) then squeezes the range of k, because a large smallest element demands a large set while simultaneously leaving fewer numbers above it to build from — that tension caps k fast. Inside each surviving case Tool #2 (Make a Systematic List) turns the leftover freedom into one plain unordered choice that a binomial coefficient counts.

1STEP 1

Name the least element

The count and the minimum are equal.

k = min B = |B|, |B| ≥ 1 → k ≥ 1
2STEP 2

Split by that value

The rest are all larger.

B = {k} ∪ C, C ⊆ {k+1, k+2, …, 12}, |C| = k - 1, |{k+1, …, 12}| = 12 - k
3STEP 3

Bound the value

There must be enough numbers above.

12 - k ≥ k - 1 ⇔ 13 ≥ 2k ⇔ k ≤ 6 (k an integer) → k ∈ {1, 2, 3, 4, 5, 6}
4STEP 4

Count with combinations

Count each case with combinations.

C(11, 0) = 1, C(10, 1) = 10, C(9, 2) = 36, C(8, 3) = 56, C(7, 4) = 35, C(6, 5) = 6
5STEP 5

Add the piles

Adding gives 144.

Σ_k=1⁶ C(12-k, k-1) = 1 + 10 + 36 + 56 + 35 + 6 = 144 → (D)
Answer
144
Two piles can be checked by hand. For k = 2 the qualifying sets are the two-element sets starting at 2: {2,3}, {2,4}, …, {2,12}, which is 10 sets, matching C(10, 1). For k = 6 a set needs six numbers all taken from {6, 7, …, 12} with 6 included; that pool has 7 numbers, so exactly one of the six numbers above 6 gets left out, giving 6 sets and matching C(6, 5). The problem's own example {4,6,8,11} falls in the k = 4 pile, where 6, 8, 11 are three numbers chosen from {5, 6, …, 12} — one of the C(8, 3) = 56 choices. The size of the answer is also sensible: there are 2¹³ = 8192 subsets in total and the rule is severe, so a count in the low hundreds fits, while choice (A) 256 = 2⁸ has the look of a stray power of two rather than a sum of binomial coefficients. Finally, the six counts 1, 10, 36, 56, 35, 6 are exactly the entries along one shallow diagonal of Pascal's triangle, and such diagonals sum to Fibonacci numbers: this one gives F₁₂ = 144, which is an independent confirmation of the arithmetic. A brute-force scan of all 8192 subsets also returns 144.
💡Key takeaway

Let the smallest element name itself: if the smallest is k, then B needs k-1 more numbers picked from the 12-k numbers above it, so add C(12-k, k-1) over every k that still fits.

  • Name the least element
  • Split the count by k
  • Bound how large k can be
  • Count each pile with combinations
  • Add the six piles

More like this

Same archetype — closest grade level first.