Difference between revisions of "2021 AMC 12A Problems/Problem 15"
MRENTHUSIASM (talk | contribs) (→Solution 1 (Without Words): I will push the bash solution to the end.) |
MRENTHUSIASM (talk | contribs) |
||
Line 3: | Line 3: | ||
<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 (Casework)== | ||
==Solution 2 (Generating Functions)== | ==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, | ||
− | <cmath> | + | <cmath>f(x,y)=\sum_{m=0}^8\sum_{n=0}^6 a_{mn}x^my^n,</cmath> |
− | f(x,y)=\sum_{m=0}^8\sum_{n=0}^6 a_{mn}x^my^n | ||
− | </cmath> | ||
where <math>a_{mn}</math> is the number of groups of <math>m</math> basses and <math>n</math> tenors. What we want to do is sum up all values of <math>a_{mn}</math> for which <math>4\mid m-n</math> except for <math>a_{00}=1</math>. To do this, define a new function | where <math>a_{mn}</math> is the number of groups of <math>m</math> basses and <math>n</math> tenors. What we want to do is sum up all values of <math>a_{mn}</math> for which <math>4\mid m-n</math> except for <math>a_{00}=1</math>. To do this, define a new function | ||
− | <cmath> | + | <cmath>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.</cmath> |
− | 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. | ||
− | </cmath> | ||
Now we just need to sum all coefficients of <math>g(x)</math> for which <math>4\mid m-n</math>. Consider a monomial <math>h(x)=x^k</math>. If <math>4\mid k</math>, | Now we just need to sum all coefficients of <math>g(x)</math> for which <math>4\mid m-n</math>. Consider a monomial <math>h(x)=x^k</math>. If <math>4\mid k</math>, | ||
− | <cmath> | + | <cmath>h(i)+h(-1)+h(-i)+h(1)=1+1+1+1=4.</cmath> |
− | h(i)+h(-1)+h(-i)+h(1)=1+1+1+1=4 | + | Otherwise, |
− | </cmath> | + | <cmath>h(i)+h(-1)+h(-i)+h(1)=0.</cmath> |
− | |||
− | <cmath> | ||
− | h(i)+h(-1)+h(-i)+h(1)=0. | ||
− | </cmath> | ||
<math>g(x)</math> is a sum of these monomials so this gives us a method to determine the sum we're looking for: | <math>g(x)</math> is a sum of these monomials so this gives us a method to determine the sum we're looking for: | ||
− | <cmath> | + | <cmath>\frac{g(i)+g(-1)+g(-i)+g(1)}{4}=2^{12}=4096.</cmath> |
− | \frac{g(i)+g(-1)+g(-i)+g(1)}{4}=2^{12}=4096 | + | (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=4095\equiv\boxed{\textbf{(D) } 95}\pmod{100}</math>. |
− | </cmath> | + | |
− | (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 | ||
~lawliet163 | ~lawliet163 | ||
Revision as of 23:07, 23 August 2021
Contents
[hide]Problem
A choir director 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 (Casework)
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 .
~lawliet163
Solution 3 (Casework and Vandermonde's Identity)
By casework, we construct the following table. In the last column, we rewrite some of the combinations using the identity We apply Vandermonde's Identity to find the requested sum:
~MRENTHUSIASM
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.