AMC 10 · 2012 · #20

Grade 8 algebra

Archetype Small-Domain Constrained Search └ Sub-archetype Sum-Target Search

base-conversionexponentsfundamental-counting-principlecomplementary-counting identify-subproblemseasier-related-problemcomplementary-counting ↑ Prerequisites: base-conversionexponents

📏 Long solution 💡 4 insights

Problem

A long product of brackets is expanded and one particular power is picked out. Find its coefficient's exponent.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Organize Information in More Ways

Nobody can multiply out 2048 terms, so Tool #15 (Organize Information in More Ways) does the real work: relabel each term of the expansion by the set of brackets that gave their x-term. That single relabelling turns "expand a huge product" into "pick a set of distinct powers of 2 that add to 2012." Tool #9 (Solve an Easier Related Problem) tests the idea on just the first three brackets, which is small enough to expand by hand. The dangerous move is to jump straight from "2012 has a binary form" to "so the coefficient is this one product" — that quietly assumes exactly one pick makes x²⁰¹², and if two picks did, their contributions would be added and the coefficient would not have to be a power of 2 at all. Tool #7 (Identify Subproblems) closes that hole: split the product one bracket at a time and show the two halves occupy separate exponent ranges, which proves every exponent from 0 to 2047 appears exactly once. Only then does Tool #11 (Work Backwards) peel powers of 2 off 2012 to find the picks, and Tool #16 (Change Focus) points at the brackets that were passed over — because those, not the chosen ones, are what build the coefficient.

1STEP 1

Label each term by its picks

Each term is named by the brackets it picks.

P(x)=Σ_{S⊆{0,…,10}}(Π_k∉ S2^k)x^Σ_k∈ S2^k=Σ_S2^(Σ_k∉ Sk)x^(Σ_k∈ S2^k)

2STEP 2

Rehearse on three brackets

Three brackets are enough to see the pattern.

(x+1)(x²+2)(x⁴+4)=x⁷+x⁶+2x⁵+2x⁴+4x³+4x²+8x+8

3STEP 3

Prove no two picks collide

No two choices can ever collide.

deg P_m=2^m+1-1 ＜ 2^m+1, so the ranges [0, 2^m+1-1] and [2^m+1, 2^m+2-1] do not overlap

4STEP 4

Back out the chosen brackets

The binary spelling names the chosen brackets.

2012=1024+512+256+128+64+16+8+4=11111011100₂

5STEP 5

Look at the brackets passed over

The brackets passed over supply the constants.

2047-2012=35=32+2+1=2⁵+2¹+2⁰

6STEP 6

Multiply the leftover constants

Multiplying them gives an exponent of 6.

1 · 2 · 32=2⁰ · 2¹ · 2⁵=2⁰⁺¹⁺⁵=2⁶=64, so a=6 → (B)

7STEP 7

Check the two ends of the polynomial

The two ends of the polynomial confirm it, choice (B).

0+1+2+…+10=55, and 1 · 2 · 4… 1024=2⁵⁵

Answer

The value a=6 is the sum of the three passed-over indices 0+1+5, and the coefficient itself is 32 · 2 · 1=64=2⁶, so the two readings agree. Three further checks. First, counting digits: 2012=11111011100₂ has eight 1s and three 0s across the 11 places k=0,…,10, matching eight brackets giving x and three giving constants. Second, range: a must lie between 0 (take every x) and 55 (take every constant), and 6 sits comfortably inside. Third, the wrong answers are exactly the slips this method avoids — 5 is what you get by using only the largest passed-over index 2⁵ and forgetting the 2 and the 1, and 10 is the index of the biggest bracket, which never enters the coefficient at all. The claim that the coefficient is a power of 2 is not an assumption here: step 3 proved only one pick makes x²⁰¹², which is why no addition of unequal terms can spoil it.

💡Key takeaway

Write the exponent you want in binary: the 1s say which brackets handed over their x, the 0s say which handed over their constant, and because no two choices can ever make the same exponent, the coefficient is simply 2 raised to the sum of the 0-positions — here 0+1+5=6.

Label each term by its picks
Rehearse on three brackets
Prove no two picks collide
Back out the chosen brackets
Look at the brackets passed over
Multiply the leftover constants
Check the two ends of the polynomial