Difference between revisions of "2016 AMC 10A Problems/Problem 20"

(Created page with "For some particular value of <math>N</math>, when <math>(a+b+c+d+1)^N</math> is expanded and like terms are combined, the resulting expression contains exactly <math>1001</mat...")
 
(Solution 2)
(22 intermediate revisions by 13 users not shown)
Line 1: Line 1:
 +
==Problem==
 
For some particular value of <math>N</math>, when <math>(a+b+c+d+1)^N</math> is expanded and like terms are combined, the resulting expression contains exactly <math>1001</math> terms that include all four variables <math>a, b,c,</math> and <math>d</math>, each to some positive power. What is <math>N</math>?
 
For some particular value of <math>N</math>, when <math>(a+b+c+d+1)^N</math> is expanded and like terms are combined, the resulting expression contains exactly <math>1001</math> terms that include all four variables <math>a, b,c,</math> and <math>d</math>, each to some positive power. What is <math>N</math>?
  
 
<math>\textbf{(A) }9 \qquad \textbf{(B) } 14 \qquad \textbf{(C) } 16 \qquad \textbf{(D) } 17 \qquad \textbf{(E) } 19</math>
 
<math>\textbf{(A) }9 \qquad \textbf{(B) } 14 \qquad \textbf{(C) } 16 \qquad \textbf{(D) } 17 \qquad \textbf{(E) } 19</math>
 +
 +
==Solution 1==
 +
All the desired terms are in the form <math>a^xb^yc^zd^w1^t</math>, where <math>x + y + z + w + t = N</math> (the <math>1^t</math> part is necessary to make stars and bars work better.)
 +
Since <math>x</math>, <math>y</math>, <math>z</math>, and <math>w</math> must be at least <math>1</math> (<math>t</math> can be <math>0</math>), let <math>x' = x - 1</math>, <math>y' = y - 1</math>, <math>z' = z - 1</math>, and <math>w' = w - 1</math>, so <math>x' + y' + z' + w' + t = N - 4</math>. Now, we use stars and bars (also known as ball and urn) to see that there are <math>\binom{(N-4)+4}{4}</math> or <math>\binom{N}{4}</math> solutions to this equation. We notice that <math>1001=7\cdot11\cdot13</math>, which leads us to guess that <math>N</math> is around these numbers. This suspicion proves to be correct, as we see that <math>\binom{14}{4} = 1001</math>, giving us our answer of <math>N=\boxed{14}</math>.
 +
 +
* An alternative is to instead make the transformation <math>t'=t+1</math>, so <math>x + y + z + w + t' = N + 1</math>, and all variables are positive integers. The solution to this, by Stars and Bars is <math>\binom{(N+1)-1}{4}=\binom{N}{4}</math> and we can proceed as above.
 +
 +
==Solution 2==
 +
 +
By [[Hockey Stick Identity]], the number of terms that have all <math>a,b,c,d</math> raised to a positive power is <math>\binom{N-1}{3}+\binom{N-2}{3}+\cdots + \binom{4}{3}+\binom{3}{3}=\binom{N}{4}</math>. We now want to find some <math>N</math> such that <math>\binom{N}{4} = 1001</math>. As mentioned above, after noticing that <math>1001 = 7\cdot11\cdot13</math>, and some trial and error, we find that <math>\binom{14}{4} = 1001</math>, giving us our answer of <math>N=\boxed{14}</math>
 +
 +
==Solution 3 (Stars and Bars)==
 +
5 sections (<math>x,y,z,w,1</math>) 4 of which need at least 1 object. <math>\dbinom{N+4-4\cdot1}{4}</math>. Test the choices and find that <math>N=\boxed{\text{(B) }14}</math>
 +
 +
==Video Solution==
 +
 +
https://www.youtube.com/watch?v=R3eJW3PCYMs
 +
 +
==Video Solution 2==
 +
https://youtu.be/TpG8wlj4eRA with 5 Stars and Bars examples preceding the solution. Time stamps in description to skip straight to solution.
 +
 +
~IceMatrix
 +
 +
==See Also==
 +
 +
{{AMC10 box|year=2016|ab=A|num-b=19|num-a=21}}
 +
{{MAA Notice}}

Revision as of 15:14, 29 November 2020

Problem

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$?

$\textbf{(A) }9 \qquad \textbf{(B) } 14 \qquad \textbf{(C) } 16 \qquad \textbf{(D) } 17 \qquad \textbf{(E) } 19$

Solution 1

All the desired terms are in the form $a^xb^yc^zd^w1^t$, where $x + y + z + w + t = N$ (the $1^t$ part is necessary to make stars and bars work better.) Since $x$, $y$, $z$, and $w$ must be at least $1$ ($t$ can be $0$), let $x' = x - 1$, $y' = y - 1$, $z' = z - 1$, and $w' = w - 1$, so $x' + y' + z' + w' + t = N - 4$. Now, we use stars and bars (also known as ball and urn) to see that there are $\binom{(N-4)+4}{4}$ or $\binom{N}{4}$ solutions to this equation. We notice that $1001=7\cdot11\cdot13$, which leads us to guess that $N$ is around these numbers. This suspicion proves to be correct, as we see that $\binom{14}{4} = 1001$, giving us our answer of $N=\boxed{14}$.

  • An alternative is to instead make the transformation $t'=t+1$, so $x + y + z + w + t' = N + 1$, and all variables are positive integers. The solution to this, by Stars and Bars is $\binom{(N+1)-1}{4}=\binom{N}{4}$ and we can proceed as above.

Solution 2

By Hockey Stick Identity, the number of terms that have all $a,b,c,d$ raised to a positive power is $\binom{N-1}{3}+\binom{N-2}{3}+\cdots + \binom{4}{3}+\binom{3}{3}=\binom{N}{4}$. We now want to find some $N$ such that $\binom{N}{4} = 1001$. As mentioned above, after noticing that $1001 = 7\cdot11\cdot13$, and some trial and error, we find that $\binom{14}{4} = 1001$, giving us our answer of $N=\boxed{14}$

Solution 3 (Stars and Bars)

5 sections ($x,y,z,w,1$) 4 of which need at least 1 object. $\dbinom{N+4-4\cdot1}{4}$. Test the choices and find that $N=\boxed{\text{(B) }14}$

Video Solution

https://www.youtube.com/watch?v=R3eJW3PCYMs

Video Solution 2

https://youtu.be/TpG8wlj4eRA with 5 Stars and Bars examples preceding the solution. Time stamps in description to skip straight to solution.

~IceMatrix

See Also

2016 AMC 10A (ProblemsAnswer KeyResources)
Preceded by
Problem 19
Followed by
Problem 21
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 10 Problems and Solutions

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