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
[hide]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,
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
Now we just need to sum all coefficients of
for which
. Consider a monomial
. If
,
otherwise,
is a sum of these monomials so this gives us a method to determine the sum we're looking for:
(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.