AMC 10 · 2007 · #25

Grade 9 countingpattern

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

recursive-sequenceset-partitioncombinations-basic easier-related-problemcaseworksystematic-enumeration ↑ Prerequisites: recursive-sequence

📏 Long solution 💡 4 insights

Problem

A subset is called spacy when no window of three consecutive numbers holds two of its members. Count the spacy subsets of the first twelve numbers.

Pick an answer.

(A)

121

(B)

123

(C)

125

(D)

127

(E)

129

How to solve

Strategy Solve an Easier Related Problem

Listing 4096 subsets by hand is out of the question, and the answer choices are two apart, so nothing approximate will do. Tool #15 (Organize Information in More Ways) does the first real work: the spacy rule is written about blocks of three consecutive integers, and it has to be rewritten as a rule about how far apart two chosen numbers may be. That rewriting is the hinge of the problem — the difference between "at least 2 apart" and "at least 3 apart" changes the answer from 377 to 129. Once the rule is about gaps, it is purely local: it never refers to the number 12. Tool #9 (Solve an Easier Related Problem) exploits that — the same question on {1,…,n} for small n is answerable by hand, and the big case is built from small ones. Tool #4 (Introduce a Variable) names those smaller answers S_n so they can be related to each other, and Tool #2 (Make a Systematic List) supplies the hand-verified base cases and then runs the recursion up to n=12. The important discipline is that the recursion must be proved, in both directions, rather than guessed from the first few terms.

1STEP 1

Windows of three become gaps of three

The window rule is really a minimum gap between members.

|S∩{n,n+1,n+2}| ≤ 1 for every n ⇔ |a-b| ≥ 3 for all distinct a,b∈ S

2STEP 2

Name the smaller problems

Naming the count for shorter ranges sets up a recursion.

S_n=#{A⊆{1,…,n} : |a-b| ≥ 3 for all distinct a,b∈ A}, target S₁₂

3STEP 3

Base cases, listed by hand

The small cases can be listed by hand.

S₀=1, S₁=2, S₂=3, S₃=4

4STEP 4

Split on whether the top number is in

Splitting on the largest number gives the recursion.

S_n=S_n-1+S_n-3 (n ≥ 3)

5STEP 5

Run the recursion up to twelve

Running it up gives 129.

S₀,…,S₁₂ = 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129

6STEP 6

Second count: sort by largest element

A second count by largest element confirms 129, choice (E).

S₁₂=1+Σ_m=1¹²S_m-3=1+(1+1+1)+(2+3+4+6+9+13+19+28+41)=1+128=129 (E)

Answer

129

The five choices are 121,123,125,127,129, an odd ladder of step 2, so estimation is useless by design and the only defence is agreement between independent exact counts. Three of them agree here. First, the recursion gives S₁₂=129. Second, the largest-element partition re-adds the whole table in a different order and also gives 129. Third, counting by subset size gives 1,12,45,56,15 for sizes 0,1,2,3,4, and 1+12+45+56+15=129; two of those are checkable by hand — for size 2 the smaller element a admits 10-a partners for a=1,…,9, giving 9+8+…+1=45, and for size 3 the middle element b admits (b-3) smaller and (10-b) larger partners for b=4,…,9, giving 1 · 6+2 · 5+3 · 4+4 · 3+5 · 2+6 · 1=56. Size is bounded by 4, since five elements would force a₅ ≥ a₁+4 · 3 ≥ 13 ＞ 12, and the size count respects that. Scale is plausible too: 129/4096≈ 3.1% of all subsets survive such a tight rule. Finally, a deliberate check on the reading of the rule: if "spacy" meant only "no two consecutive" (gap at least 2), the same argument would give S_n=S_n-1+S_n-2 and hence the Fibonacci value 377 — far outside the answer list, which confirms the gap-at-least-3 reading is the intended one.

💡Key takeaway

Spacy really means the chosen numbers sit at least three apart, so taking the biggest one wipes out the two slots below it and leaves the very same puzzle three numbers shorter.

Windows of three become gaps of three
Name the smaller problems
Base cases, listed by hand
Split on whether the top number is in
Run the recursion up to twelve
Second count: sort by largest element