2016 AMC 10A Problem 20

P16-20~4 minPrint

Distributions & Stars and Bars Polynomials Map the objects to something easier to count Set up the equation/formula and compute; no special trick needed

For some particular value of $N$ , when $(a+b+c+d+1)^N$ is expanded and like terms are combined, the resulting expression contains exactly $1001$ terms that include all four variables $a, b,c,$ and $d$ , each to some positive power. What is $N$ ?

Show solution without answering

Key insight

Each term records how many brackets give a, b, c, d or 1. With every letter used at least once, stars and bars gives N choose 4.

Solution

Step 1: what a term looks like. Expanding $(a + b + c + d + 1)^N$ means choosing one item from each of the $N$ brackets and multiplying. After like terms are combined, a term is decided by how many brackets gave $a$ , how many gave $b$ , $c$ , $d$ , and how many gave $1$ . Call these counts $i, j, k, l$ and $m$ . They add up to $N$ :
$i + j + k + l + m = N.$
Different lists of counts give different terms, so we are counting lists.

Step 2: small example. Take $N = 5$ . Each of $a, b, c, d$ needs at least one bracket, which uses $4$ of the $5$ brackets. The last bracket can give $a$ , $b$ , $c$ , $d$ or $1$ , so the terms are $a^2bcd$ , $ab^2cd$ , $abc^2d$ , $abcd^2$ and $abcd$ : $5$ terms. Keep this check in mind.

Step 3: force each letter to appear. We need $i, j, k, l$ all at least $1$ . Give each letter its one required bracket first. That uses $4$ brackets and leaves $N - 4$ brackets to hand out freely among the five kinds ( $a, b, c, d, 1$ ), where any kind may get zero.

Step 4: count with stars and bars. Handing out $N - 4$ identical items to $5$ kinds is the same as lining up $N - 4$ stars and $4$ bars (the bars split the line into $5$ groups). That is $N$ symbols, and we choose which $4$ of them are bars:
$\binom{N}{4}.$
For $N = 5$ this gives $5$ , matching step 2.

Step 5: solve $\binom{N}{4} = 1001$ . Note $1001 = 7 \cdot 11 \cdot 13$ . Try $N = 14$ :
$\binom{14}{4} = \frac{14 \cdot 13 \cdot 12 \cdot 11}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{24024}{24} = 1001.$
It matches, and $\binom{N}{4}$ grows as $N$ grows, so $N = 14$ is the only answer.

The answer is $\boxed{\textbf{(B)}\ 14}$ .

Why this works

Counting different terms in an expansion means counting the different ways to split the power among the pieces. The constant $1$ acts like a fifth letter that soaks up whatever is left over. "Each letter at least once" is handled by giving each letter one bracket first, and then stars and bars counts the rest.

Alternative approach

Since the count is $\binom{N}{4}$ , test the choices: $\binom{9}{4} = 126$ , $\binom{14}{4} = 1001$ , $\binom{16}{4} = 1820$ . Only $14$ works.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

After combining like terms, each distinct term is $a^i b^j c^k d^l$ where the exponents record how many of the $N$ factors contributed $a$ , $b$ , $c$ , $d$ , or $1$ . If $m$ factors contributed the $1$ , then
$i + j + k + l + m = N, \qquad m \ge 0.$

We want the terms with $i, j, k, l \ge 1$ . Give each of $a, b, c, d$ one forced unit: set $i' = i-1$ , etc. Then $i' + j' + k' + l' + m = N - 4$ with all five variables nonnegative. By stars and bars the number of solutions is
$\binom{(N-4) + 4}{4} = \binom{N}{4}.$

Set $\binom{N}{4} = 1001 = 7 \cdot 11 \cdot 13$ . Since $\binom{14}{4} = \frac{14\cdot 13\cdot 12\cdot 11}{24} = 1001$ , we get $N = 14$ . (The function $\binom{N}{4}$ is increasing, so this is the only solution.)

The answer is $\boxed{\textbf{(B)}\ 14}$ .

Review in the AoPS books

Intermediate Counting & Probability, Chapter 7: Distributions (§7.2, §7.3)
Intermediate Algebra, Chapter 6: Polynomial Division (§6.2, §6.4)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.4)