Difference between revisions of "2021 AMC 12A Problems/Problem 15"
Lawliet163 (talk | contribs) (→Solution 5: Generating Functions) |
MRENTHUSIASM (talk | contribs) (Put all video solutions at the end.) |
||
| Line 4: | Line 4: | ||
<math>\textbf{(A) } 47\qquad\textbf{(B) } 48\qquad\textbf{(C) } 83\qquad\textbf{(D) } 95\qquad\textbf{(E) } 96\qquad</math> | <math>\textbf{(A) } 47\qquad\textbf{(B) } 48\qquad\textbf{(C) } 83\qquad\textbf{(D) } 95\qquad\textbf{(E) } 96\qquad</math> | ||
| − | == | + | ==Solution 1== |
| − | |||
| − | |||
| − | |||
We know the choose function and we know the pair multiplication <math>MN</math> so we do the multiplications and additions. | We know the choose function and we know the pair multiplication <math>MN</math> so we do the multiplications and additions. | ||
<math>\binom{6}{0}\left(\binom{8}{4}+\binom{8}{8}\right)+\binom{6}{1}\left(\binom{8}{1}+\binom{8}{5}\right)+\binom{6}{2}\left(\binom{8}{2}+\binom{8}{6}\right)+\binom{6}{3}\left(\binom{8}{3}+\binom{8}{7}\right)+\\\binom{6}{4}\left(\binom{8}{0}+\binom{8}{4}+\binom{8}{8}\right)+\binom{6}{5}\left(\binom{8}{1}+\binom{8}{5}\right)+\binom{6}{6}\left(\binom{8}{2}+\binom{8}{6}\right) = \boxed{(D) 4095}</math> | <math>\binom{6}{0}\left(\binom{8}{4}+\binom{8}{8}\right)+\binom{6}{1}\left(\binom{8}{1}+\binom{8}{5}\right)+\binom{6}{2}\left(\binom{8}{2}+\binom{8}{6}\right)+\binom{6}{3}\left(\binom{8}{3}+\binom{8}{7}\right)+\\\binom{6}{4}\left(\binom{8}{0}+\binom{8}{4}+\binom{8}{8}\right)+\binom{6}{5}\left(\binom{8}{1}+\binom{8}{5}\right)+\binom{6}{6}\left(\binom{8}{2}+\binom{8}{6}\right) = \boxed{(D) 4095}</math> | ||
| Line 13: | Line 10: | ||
~Lopkiloinm | ~Lopkiloinm | ||
| − | == | + | ==Solution 2: Generating Functions== |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
The problem can be done using a roots of unity filter. Let <math>f(x,y)=(1+x)^8(1+y)^6</math>. By expanding the binomials and distributing, <math>f(x,y)</math> is the generating function for different groups of basses and tenors. That is, | The problem can be done using a roots of unity filter. Let <math>f(x,y)=(1+x)^8(1+y)^6</math>. By expanding the binomials and distributing, <math>f(x,y)</math> is the generating function for different groups of basses and tenors. That is, | ||
| Line 45: | Line 34: | ||
(since <math>g(-1)=0</math> and it can be checked that <math>g(i)=-g(-i)</math>). Hence, the answer is <math>4096-1</math> with the <math>-1</math> for <math>a_{00}</math> which gives <math>\boxed{95}</math>. | (since <math>g(-1)=0</math> and it can be checked that <math>g(i)=-g(-i)</math>). Hence, the answer is <math>4096-1</math> with the <math>-1</math> for <math>a_{00}</math> which gives <math>\boxed{95}</math>. | ||
~lawliet163 | ~lawliet163 | ||
| + | |||
| + | ==Video Solution by Punxsutawney Phil== | ||
| + | https://youtube.com/watch?v=FD9BE7hpRvg&t=533s | ||
| + | |||
| + | ==Video Solution by Hawk Math== | ||
| + | https://www.youtube.com/watch?v=AjQARBvdZ20 | ||
| + | |||
| + | ==Video Solution by OmegaLearn (using Vandermonde's Identity)== | ||
| + | https://www.youtube.com/watch?v=mki7xtZLk1I | ||
| + | |||
| + | ~pi_is_3.14 | ||
==See also== | ==See also== | ||
Revision as of 17:27, 13 February 2021
Contents
Problem
A choir direction must select a group of singers from among his 
tenors and 
basses. The only requirements are that the difference between the number of tenors and basses must be a multiple of 
, and the group must have at least one singer. Let 
be the number of different groups that could be selected. What is the remainder when is divided by 
?
Solution 1
We know the choose function and we know the pair multiplication 
so we do the multiplications and additions.
~Lopkiloinm
Solution 2: Generating Functions
The problem can be done using a roots of unity filter. Let 
. By expanding the binomials and distributing, 
is the generating function for different groups of basses and tenors. That is,
![\[f(x,y)=\sum_{m=0}^8\sum_{n=0}^6 a_{mn}x^my^n\]](http://latex.artofproblemsolving.com/e/9/a/e9a3a22868b72af233504c5a65b3d8c384bbe4ef.png)
where 
is the number of groups of 
basses and 
tenors. What we want to do is sum up all values of for which 
except for 
. To do this, define a new function
![\[g(x)=f(x,x^{-1})=\sum_{m=0}^8\sum_{n=0}^6 a_{mn}x^{m-n}=(1+x)^8(1+x^{-1})^6.\]](http://latex.artofproblemsolving.com/7/1/4/71431dc95542210ebc2cb83f54637a1e97b76327.png)
Now we just need to sum all coefficients of 
for which . Consider a monomial 
. If 
,
![\[h(i)+h(-1)+h(-i)+h(1)=1+1+1+1=4\]](http://latex.artofproblemsolving.com/c/7/5/c75b945f54a459e95c7f40db7bbb1a73ffa79445.png)
otherwise,
![\[h(i)+h(-1)+h(-i)+h(1)=0.\]](http://latex.artofproblemsolving.com/2/3/2/232f9e4ee70f60db6a168f635390a14eb77da314.png)
is a sum of these monomials so this gives us a method to determine the sum we're looking for:
![\[\frac{g(i)+g(-1)+g(-i)+g(1)}{4}=2^{12}=4096\]](http://latex.artofproblemsolving.com/3/9/e/39e5dcbe69d370ec5ff67a6e4851170892d9dfd5.png)
(since 
and it can be checked that 
). Hence, the answer is 
with the 
for 
which gives 
.
~lawliet163
Video Solution by Punxsutawney Phil
https://youtube.com/watch?v=FD9BE7hpRvg&t=533s
Video Solution by Hawk Math
https://www.youtube.com/watch?v=AjQARBvdZ20
Video Solution by OmegaLearn (using Vandermonde's Identity)
https://www.youtube.com/watch?v=mki7xtZLk1I
~pi_is_3.14
See also
| 2021 AMC 12A (Problems • Answer Key • Resources) | |
| Preceded by Problem 14 |
Followed by Problem 16 |
| 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. 
