Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 AMC 12A Problems/Problem 24"

m
(→‎Solution)
Line 35: Line 35:
  
 
Subtract this number from 2015028 we obtain <math>D. 1008016</math> as our answer.
 
Subtract this number from 2015028 we obtain <math>D. 1008016</math> as our answer.
 +
 +
 +
Alternatively, we can use a generating function to solve this problem.
 +
The goal is to find the generating function for the number of unique terms in the simplified expression (in terms of <math>k</math>). In other words, we want to find <math>f(x)</math> where the coefficient of <math>x^k</math> equals the number of unique terms in <math>(x+y+z)^k + (x-y-z)^k</math>.
 +
 +
 +
First, we note that all unique terms in the expression have the form, <math>Cx^ay^bz^c</math>, where <math>a+b+c=k</math> and <math>C</math> is some constant. Therefore, the generating function for the MAXIMUM number of unique terms possible in the simplified expression of <math>(x+y+z)^k + (x-y-z)^k</math> is
 +
<cmath>(1+x+x^2+x^3\cdots)^3 = \frac{1}{(1-x)^3}</cmath>
 +
 +
 +
Secondly, we note that a certain number of terms of the form, <math>Cx^ay^bz^c</math>, do not appear in the simplified version of our expression because those terms cancel. Specifically, we observe that terms cancel when <math>1 \equiv b+c\text{ (mod }2\text{)}</math> because every unique term is of the form:
 +
<cmath>\binom{k}{a,b,c}x^ay^bz^c+(-1)^{b+c}\binom{k}{a,b,c}x^ay^bz^c</cmath>
 +
for all possible <math>a,b,c</math>.
 +
 +
 +
Since the generating function for the maximum number of unique terms is already known, it is logical that we want to find the generating function for the number of terms that cancel, also in terms of <math>k</math>. With some thought, we see that this desired generating function is the following:
 +
<cmath>2(x+x^3+x^5\cdots)(1+x^2+x^4\cdots)(1+x+x^2+x^3\cdots) = \frac{2x}{(1-x)^3(1+x)^2}</cmath>
 +
 +
 +
Now, we want to subtract the latter from the former in order to get the generating function for the number of unique terms in <math>(x+y+z)^k + (x-y-z)^k</math>, our initial goal:
 +
<cmath>\frac{1}{(1-x)^3}-\frac{2x}{(1-x)^3(1+x)^2} = \frac{x^2+1}{(1-x)^3(1+x)^2}</cmath>
 +
which equals
 +
<cmath>(x^2+1)(1+x+x^2\cdots)^3(1-x+x^2-x^3\cdots)^2</cmath>
 +
 +
 +
The coefficient of <math>x^{2006}</math> of the above expression equals
 +
<cmath>\sum_{a=0}^{2006}\binom{2+a}{2}\binom{1+2006-a}{1}(-1)^a + \sum_{a=0}^{2004}\binom{2+a}{2}\binom{1+2004-a}{1}(-1)^a</cmath>
 +
 +
 +
Evaluating the expression, we get <math>1008016</math>, as expected.
  
 
== See also ==
 
== See also ==

Revision as of 02:47, 14 July 2008

Problem

The expression

$(x+y+z)^{2006}+(x-y-z)^{2006}$

is simplified by expanding it and combining like terms. How many terms are in the simplified expression?

$\mathrm{(A) \ } 6018\qquad \mathrm{(B) \ } 671,676\qquad \mathrm{(C) \ } 1,007,514\qquad \mathrm{(D) \ } 1,008,016\qquad\mathrm{(E) \ } 2,015,028$

Solution

By the Multinomial Theorem, the summands can be written as

\[\sum_{a+b+c=2006}{\frac{2006!}{a!b!c!}x^ay^bz^c}\]

and

\[\sum_{a+b+c=2006}{\frac{2006!}{a!b!c!}x^a(-y)^b(-z)^c},\]

respectively. Since the coefficients of like terms are the same in each expression, each like term either cancel one another out or the coefficient doubles. In each expansion there are:

\[{2006+2\choose 2} = 2015028\]

terms without cancellation. For any term in the second expansion to be negative, the parity of the exponents of $y$ and $z$ must be opposite. Now we find a pattern:

if the exponent of $y$ is 1, the exponent of $z$ can be all even integers up to 2004, so 1003 terms.

if the exponent of $y$ is 3, the exponent of $z$ can go up to 2002, so 1002 terms.

$\vdots$

if the exponent of $y$ is 2005, then $z$ can only be 0. So 1 term.

add them up we get $\frac{1003\cdot1004}{2}$ terms. However, we can switch the exponents of $y$ and $z$ and these terms will still have a negative sign. So there are a total of $1003\cdot1004$ negative terms.

Subtract this number from 2015028 we obtain $D. 1008016$ as our answer.


Alternatively, we can use a generating function to solve this problem. The goal is to find the generating function for the number of unique terms in the simplified expression (in terms of $k$). In other words, we want to find $f(x)$ where the coefficient of $x^k$ equals the number of unique terms in $(x+y+z)^k + (x-y-z)^k$.


First, we note that all unique terms in the expression have the form, $Cx^ay^bz^c$, where $a+b+c=k$ and $C$ is some constant. Therefore, the generating function for the MAXIMUM number of unique terms possible in the simplified expression of $(x+y+z)^k + (x-y-z)^k$ is \[(1+x+x^2+x^3\cdots)^3 = \frac{1}{(1-x)^3}\]


Secondly, we note that a certain number of terms of the form, $Cx^ay^bz^c$, do not appear in the simplified version of our expression because those terms cancel. Specifically, we observe that terms cancel when $1 \equiv b+c\text{ (mod }2\text{)}$ because every unique term is of the form: \[\binom{k}{a,b,c}x^ay^bz^c+(-1)^{b+c}\binom{k}{a,b,c}x^ay^bz^c\] for all possible $a,b,c$.


Since the generating function for the maximum number of unique terms is already known, it is logical that we want to find the generating function for the number of terms that cancel, also in terms of $k$. With some thought, we see that this desired generating function is the following: \[2(x+x^3+x^5\cdots)(1+x^2+x^4\cdots)(1+x+x^2+x^3\cdots) = \frac{2x}{(1-x)^3(1+x)^2}\]


Now, we want to subtract the latter from the former in order to get the generating function for the number of unique terms in $(x+y+z)^k + (x-y-z)^k$, our initial goal: \[\frac{1}{(1-x)^3}-\frac{2x}{(1-x)^3(1+x)^2} = \frac{x^2+1}{(1-x)^3(1+x)^2}\] which equals \[(x^2+1)(1+x+x^2\cdots)^3(1-x+x^2-x^3\cdots)^2\]


The coefficient of $x^{2006}$ of the above expression equals \[\sum_{a=0}^{2006}\binom{2+a}{2}\binom{1+2006-a}{1}(-1)^a + \sum_{a=0}^{2004}\binom{2+a}{2}\binom{1+2004-a}{1}(-1)^a\]


Evaluating the expression, we get $1008016$, as expected.

See also

2006 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AMC_12A_Problems/Problem_24&oldid=27040"