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 "2008 AMC 12A Problems/Problem 19"

m (→‎Solution)
(→‎Solution 1)
 
(17 intermediate revisions by 12 users not shown)
Line 6: Line 6:
 
<math>\mathrm{(A)}\ 195\qquad\mathrm{(B)}\ 196\qquad\mathrm{(C)}\ 224\qquad\mathrm{(D)}\ 378\qquad\mathrm{(E)}\ 405</math>
 
<math>\mathrm{(A)}\ 195\qquad\mathrm{(B)}\ 196\qquad\mathrm{(C)}\ 224\qquad\mathrm{(D)}\ 378\qquad\mathrm{(E)}\ 405</math>
  
−
==Solution==  
+
==Solution 1 (easiest)==  
 
Let <math>A = \left(1 + x + x^2 + \cdots + x^{14}\right)</math> and <math>B = \left(1 + x + x^2 + \cdots + x^{27}\right)</math>. We are expanding <math>A \cdot A \cdot B</math>.  
 
Let <math>A = \left(1 + x + x^2 + \cdots + x^{14}\right)</math> and <math>B = \left(1 + x + x^2 + \cdots + x^{27}\right)</math>. We are expanding <math>A \cdot A \cdot B</math>.  
  
−
Since there are <math>15</math> terms in <math>A</math>, there are <math>15^2 = 225</math> ways to choose one term from each <math>A</math>. The product of the selected terms is <math>x^n</math> for some integer <math>n</math> between <math>0</math> and <math>28</math> inclusive. For each <math>n \neq 0</math>, there is one and only one <math>x^{28 - n}</math> in <math>B</math>. For example, if I choose <math>x^2</math> from <math>A</math> , then there is exactly one power of <math>x</math> in <math>B</math> that I can choose; in this case, it would be <math>x^(24)</math>. Since there is only one way to choose one term from each <math>A</math> to get a product of <math>x^0</math>, there are <math>225 - 1 = 224</math> ways to choose one term from each <math>A</math> and one term from <math>B</math> to get a product of <math>x^{28}</math>. Thus the coefficient of the <math>x^{28}</math> term is <math>224 \Rightarrow C</math>.
+
Since there are <math>15</math> terms in <math>A</math>, there are <math>15^2 = 225</math> ways to choose one term from each <math>A</math>. The product of the selected terms is <math>x^n</math> for some integer <math>n</math> between <math>0</math> and <math>28</math> inclusive. For each <math>n \neq 0</math>, there is one and only one <math>x^{28 - n}</math> in <math>B</math>. For example, if I choose <math>x^2</math> from <math>A</math> , then there is exactly one power of <math>x</math> in <math>B</math> that I can choose; in this case, it would be <math>x^{24}</math>. Since there is only one way to choose one term from each <math>A</math> to get a product of <math>x^0</math>, there are <math>225 - 1 = 224</math> ways to choose one term from each <math>A</math> and one term from <math>B</math> to get a product of <math>x^{28}</math>. Thus the coefficient of the <math>x^{28}</math> term is <math>224 \Rightarrow \boxed{C}</math>.
 +
 
 +
== Solution 2 ==
 +
Let <math>P(x) = \left(1 + x + x^2 + \cdots + x^{14}\right)^2 = a_0 + a_1x + a_2x^2 + \cdots + a_{28}x^{28}</math>. Then the <math>x^{28}</math> term from the product in question <math>\left(1 + x + x^2 + \cdots + x^{27}\right)(a_0 + a_1x + a_2x^2 + \cdots + a_{28}x^{28})</math> is
 +
 
 +
<math>1a_{28}x^{28} + xa_{27}x^{27} + x^2a_{26}x^{26} + \cdots + x^{27}a_1x = \left(a_1 + a_2 + \cdots a_{28}\right)x^{28}</math>
 +
 
 +
So we are trying to find the sum of the coefficients of <math>P(x)</math> minus <math>a_0</math>. Since the constant term <math>a_0</math> in <math>P(x)</math> (when expanded) is <math>1</math>, and the sum of the coefficients of <math>P(x)</math> is <math>P(1)</math>, we find the answer to be
 +
<math>P(1) - a_0
 +
= \left(1 + 1 + 1^2 + \cdots 1^{14}\right)^2 - 1
 +
= 15^2 - 1
 +
= 224 \Rightarrow \boxed{C}</math>.
 +
 
 +
==Solution 3==
 +
We expand <math>(1 + x + x^2 + x^3 + \cdots + x^{14})^2</math> to <math>(1 + x + x^2 + x^3 + \cdots + x^{14}) * (1 + x + x^2 + x^3 + \cdots + x^{14})</math> and use FOIL to multiply. It expands out to:
 +
 
 +
<math>1 + x + x^2 + x^3 + x^4 + \cdots + x^{14} + </math> 
 +
 
 +
<math>\qquad x + x^2 + x^3 + x^4 + \cdots + x^{14} + x^{15} + </math>
 +
 
 +
<math>\qquad \qquad x^2 + x^3 + x^4 + \cdots + x^{14} + x^{15} + x^{16} + \cdots</math>
 +
 
 +
It becomes apparent that
 +
 
 +
<math>(1 + x + x^2 + x^3 + \cdots + x^{14})^2 = 1 + 2x + 3x^2 + 4x^3 + \cdots + 15x^{14} + 14x^{15} + 13x^{16} + \cdots + x^{28}</math>.
 +
 
 +
Now we have to find the coefficient of <math>x^{28}</math> in the product:
 +
 
 +
<math>(1 + 2x + 3x^2 + 4x^3 + \cdots + 15x^{14} + 14x^{15} + 13x^{16} + \cdots + x^{28}) \cdot (1 + x + x^2 + x^3 + \cdots + x^{27})</math>.
 +
 
 +
We quickly see that the we get <math>x^{28}</math> terms from <math>x^{27} \cdot 2x</math>, <math>x^{26} \cdot 3x^2</math>, <math>x^{25} \cdot 4x^3</math>, ... <math>15x^{14} \cdot x^{14}</math>, ... <math>x^{28} \cdot 1</math>. The coefficient of <math>x^{28}</math> is just the sum of the coefficients of all these terms. <math>1 + 2 + 3 + 4 + \cdots + 15 + 14 + 13 + \cdots + 4 + 3 + 2 = 224</math>, so the answer is <math>\boxed{C}</math>.
 +
 
 +
==Solution 4==
 +
Rewrite the product as <math>\frac{(x^{28} - 1)(x^{15} - 1)(x^{15} - 1)}{(x - 1)^3}</math>. It is known that
 +
 
 +
<cmath>\frac{1}{(1 - x)^n} = \binom{n - 1}{n - 1} + \binom{n}{n - 1}x + \binom{n + 1}{n - 1}x^2 + \binom{n + 2}{n - 1}x^3 + \cdots + \binom{n - 1 + k}{n - 1}x^k + \cdots .</cmath>
 +
 
 +
Thus, our product becomes
 +
 
 +
<cmath>-\left( x^{28} - 1 \right) \left( x^{15} - 1 \right) \left( x^{15} - 1 \right) \left( \binom{2}{2} + \binom{3}{2}x + \binom{4}{2}x^2 + \cdots \right).</cmath>
 +
 
 +
<cmath>= -\left( x^{28} - 1 \right) \left( x^{15} - 1 \right) \left( x^{15} - 1 \right) \left( 1 + 3x + 6x^2 + \cdots \right). </cmath>
 +
 
 +
We determine the <math>x^{28}</math> coefficient by doing casework on the first three terms in our product. We can obtain an <math>x^{28}</math> term by choosing <math>x^{28}</math> in the first term, <math>-1</math> in the second and third terms, and <math>1</math> in the fourth term. We can get two <math>x^{28}</math> terms by choosing <math>x^{15}</math> in either the second or third term, <math>-1</math> in the first term, <math>-1</math> in the second or third term from which <math>x^{15}</math> has not been chosen, and the <math>\binom{15}{2}x^{13}</math> in the fourth term. We get <math>\binom{15}{2} * 2 = 210</math> <math>x^{28}</math> terms this way. (We multiply by <math>2</math> because the <math>x^{15}</math> term could have been chosen from the second term or the third term). Lastly, we can get an <math>x^{28}</math> term by choosing <math>-1</math> in the first three terms and a <math>\binom{30}{2}x^{28}</math> from the fourth term. We have a total of <math>1 + 210 - 435 = -224</math> for the <math>x^{28}</math> coefficient, but we recall that we have a negative sign in front of our product, so we obtain an answer of <math>224 \Rightarrow \boxed{(C)}</math>.
  
 
==See Also==
 
==See Also==
 +
 
{{AMC12 box|year=2008|ab=A|num-b=18|num-a=20}}
 
{{AMC12 box|year=2008|ab=A|num-b=18|num-a=20}}
  
 
[[Category:Introductory Algebra Problems]]
 
[[Category:Introductory Algebra Problems]]
 +
{{MAA Notice}}

Latest revision as of 21:54, 9 January 2021

Problem

In the expansion of \[\left(1 + x + x^2 + \cdots + x^{27}\right)\left(1 + x + x^2 + \cdots + x^{14}\right)^2,\] what is the coefficient of $x^{28}$?

$\mathrm{(A)}\ 195\qquad\mathrm{(B)}\ 196\qquad\mathrm{(C)}\ 224\qquad\mathrm{(D)}\ 378\qquad\mathrm{(E)}\ 405$

Solution 1 (easiest)

Let $A = \left(1 + x + x^2 + \cdots + x^{14}\right)$ and $B = \left(1 + x + x^2 + \cdots + x^{27}\right)$. We are expanding $A \cdot A \cdot B$.

Since there are $15$ terms in $A$, there are $15^2 = 225$ ways to choose one term from each $A$. The product of the selected terms is $x^n$ for some integer $n$ between $0$ and $28$ inclusive. For each $n \neq 0$, there is one and only one $x^{28 - n}$ in $B$. For example, if I choose $x^2$ from $A$ , then there is exactly one power of $x$ in $B$ that I can choose; in this case, it would be $x^{24}$. Since there is only one way to choose one term from each $A$ to get a product of $x^0$, there are $225 - 1 = 224$ ways to choose one term from each $A$ and one term from $B$ to get a product of $x^{28}$. Thus the coefficient of the $x^{28}$ term is $224 \Rightarrow \boxed{C}$.

Solution 2

Let $P(x) = \left(1 + x + x^2 + \cdots + x^{14}\right)^2 = a_0 + a_1x + a_2x^2 + \cdots + a_{28}x^{28}$. Then the $x^{28}$ term from the product in question $\left(1 + x + x^2 + \cdots + x^{27}\right)(a_0 + a_1x + a_2x^2 + \cdots + a_{28}x^{28})$ is

$1a_{28}x^{28} + xa_{27}x^{27} + x^2a_{26}x^{26} + \cdots + x^{27}a_1x = \left(a_1 + a_2 + \cdots a_{28}\right)x^{28}$

So we are trying to find the sum of the coefficients of $P(x)$ minus $a_0$. Since the constant term $a_0$ in $P(x)$ (when expanded) is $1$, and the sum of the coefficients of $P(x)$ is $P(1)$, we find the answer to be $P(1) - a_0 = \left(1 + 1 + 1^2 + \cdots 1^{14}\right)^2 - 1 = 15^2 - 1 = 224 \Rightarrow \boxed{C}$.

Solution 3

We expand $(1 + x + x^2 + x^3 + \cdots + x^{14})^2$ to $(1 + x + x^2 + x^3 + \cdots + x^{14}) * (1 + x + x^2 + x^3 + \cdots + x^{14})$ and use FOIL to multiply. It expands out to:

$1 + x + x^2 + x^3 + x^4 + \cdots + x^{14} +$

$\qquad x + x^2 + x^3 + x^4 + \cdots + x^{14} + x^{15} +$

$\qquad \qquad x^2 + x^3 + x^4 + \cdots + x^{14} + x^{15} + x^{16} + \cdots$

It becomes apparent that

$(1 + x + x^2 + x^3 + \cdots + x^{14})^2 = 1 + 2x + 3x^2 + 4x^3 + \cdots + 15x^{14} + 14x^{15} + 13x^{16} + \cdots + x^{28}$.

Now we have to find the coefficient of $x^{28}$ in the product:

$(1 + 2x + 3x^2 + 4x^3 + \cdots + 15x^{14} + 14x^{15} + 13x^{16} + \cdots + x^{28}) \cdot (1 + x + x^2 + x^3 + \cdots + x^{27})$.

We quickly see that the we get $x^{28}$ terms from $x^{27} \cdot 2x$, $x^{26} \cdot 3x^2$, $x^{25} \cdot 4x^3$, ... $15x^{14} \cdot x^{14}$, ... $x^{28} \cdot 1$. The coefficient of $x^{28}$ is just the sum of the coefficients of all these terms. $1 + 2 + 3 + 4 + \cdots + 15 + 14 + 13 + \cdots + 4 + 3 + 2 = 224$, so the answer is $\boxed{C}$.

Solution 4

Rewrite the product as $\frac{(x^{28} - 1)(x^{15} - 1)(x^{15} - 1)}{(x - 1)^3}$. It is known that

\[\frac{1}{(1 - x)^n} = \binom{n - 1}{n - 1} + \binom{n}{n - 1}x + \binom{n + 1}{n - 1}x^2 + \binom{n + 2}{n - 1}x^3 + \cdots + \binom{n - 1 + k}{n - 1}x^k + \cdots .\]

Thus, our product becomes

\[-\left( x^{28} - 1 \right) \left( x^{15} - 1 \right) \left( x^{15} - 1 \right) \left( \binom{2}{2} + \binom{3}{2}x + \binom{4}{2}x^2 + \cdots \right).\]

\[= -\left( x^{28} - 1 \right) \left( x^{15} - 1 \right) \left( x^{15} - 1 \right) \left( 1 + 3x + 6x^2 + \cdots \right).\]

We determine the $x^{28}$ coefficient by doing casework on the first three terms in our product. We can obtain an $x^{28}$ term by choosing $x^{28}$ in the first term, $-1$ in the second and third terms, and $1$ in the fourth term. We can get two $x^{28}$ terms by choosing $x^{15}$ in either the second or third term, $-1$ in the first term, $-1$ in the second or third term from which $x^{15}$ has not been chosen, and the $\binom{15}{2}x^{13}$ in the fourth term. We get $\binom{15}{2} * 2 = 210$ $x^{28}$ terms this way. (We multiply by $2$ because the $x^{15}$ term could have been chosen from the second term or the third term). Lastly, we can get an $x^{28}$ term by choosing $-1$ in the first three terms and a $\binom{30}{2}x^{28}$ from the fourth term. We have a total of $1 + 210 - 435 = -224$ for the $x^{28}$ coefficient, but we recall that we have a negative sign in front of our product, so we obtain an answer of $224 \Rightarrow \boxed{(C)}$.

See Also

2008 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 18 		Followed by
Problem 20
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_AMC_12A_Problems/Problem_19&oldid=141809"