Difference between revisions of "2021 AMC 12A Problems/Problem 15"
MRENTHUSIASM (talk | contribs) m (→Solution 4 (Combinatoric Argument)) |
Ericzzzqwq (talk | contribs) (→Solution 2 (Vandermonde's Identity)) |
||
(39 intermediate revisions by 7 users not shown) | |||
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 ( | + | ==Solution 1 (Bijection)== |
− | < | + | Suppose that <math>t</math> tenors and <math>b</math> basses are selected. The requirements are <math>t\equiv b\pmod{4}</math> and <math>(t,b)\neq(0,0).</math> |
− | \ | + | |
− | \ | + | It follows that <math>b'=8-b</math> basses are not selected. Since the ordered pairs <math>(t,b)</math> and the ordered pairs <math>(t,b')</math> have one-to-one correspondence, we consider the ordered pairs <math>(t,b')</math> instead. The requirements become <math>t\equiv8-b'\pmod{4}</math> and <math>(t,8-b')\neq(0,0),</math> which simplify to <math>t+b'\equiv0\pmod{4}</math> and <math>(t,b')\neq(0,8),</math> respectively. |
− | 0 | + | |
− | + | As <math>t+b'\in\{0,4,8,12\},</math> the total number of such groups is | |
− | + | <cmath>\begin{align*} | |
− | + | N&=\binom{14}{0}+\binom{14}{4}+\left[\binom{14}{8}-1\right]+\binom{14}{12} \ | |
− | + | &=\binom{14}{0}+\binom{14}{4}+\left[\binom{14}{6}-1\right]+\binom{14}{2} \\ | |
− | + | &=1+1001+[3003-1]+91 \ | |
− | + | &=4095, | |
− | \ | + | \end{align*}</cmath> |
+ | from which <math>N\equiv\boxed{\textbf{(D) } 95}\pmod{100}.</math> | ||
+ | |||
+ | ~MRENTHUSIASM | ||
+ | |||
+ | ==Solution 2 (Vandermonde's Identity)== | ||
+ | Suppose that <math>t</math> tenors and <math>b</math> basses are selected. The requirements are <math>t\equiv b\pmod{4}</math> and <math>(t,b)\neq(0,0).</math> | ||
+ | |||
+ | Note that <math>\binom{6}{t}\binom{8}{b}</math> different groups can be formed by selecting <math>t</math> tenors and <math>b</math> basses. Since <math>t-b\in\{-8,-4,0,4\},</math> we apply casework: | ||
+ | <ol style="margin-left: 1.5em;"> | ||
+ | <li>If <math>t-b=-8,</math> then <math>\binom{6}{0}\binom{8}{8}</math> different group can be formed.</li><p> | ||
+ | <li>If <math>t-b=-4,</math> then <math>\sum_{k=0}^{4}\binom{6}{k}\binom{8}{k+4}</math> different groups can be formed.</li><p> | ||
+ | <li>If <math>t-b=0,</math> then <math>\left[\sum_{k=0}^{6}\binom{6}{k}\binom{8}{k}\right]-1</math> different groups can be formed, recalling that <math>(t,b)\neq(0,0).</math></li><p> | ||
+ | <li>If <math>t-b=4,</math> then <math>\sum_{k=0}^{2}\binom{6}{k+4}\binom{8}{k}</math> different groups can be formed.</li><p> | ||
+ | </ol> | ||
+ | By the combinatorial identity <math>\binom{n}{k}=\binom{n}{n-k}</math> and Vandermonde's Identity <math>\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r},</math> we find the total number of such groups: | ||
+ | <cmath>\begin{align*} | ||
+ | N&=\binom{6}{0}\binom{8}{8}+\left[\sum_{k=0}^{4}\binom{6}{k}\binom{8}{k+4}\right]+\left[\left[\sum_{k=0}^{6}\binom{6}{k}\binom{8}{k}\right]-1\right]+\left[\sum_{k=0}^{2}\binom{6}{k+4}\binom{8}{k}\right] \ | ||
+ | &=\binom{6}{0}\binom{8}{0}+\left[\sum_{k=0}^{4}\binom{6}{k}\binom{8}{4-k}\right]+\left[\left[\sum_{k=0}^{6}\binom{6}{6-k}\binom{8}{k}\right]-1\right]+\left[\sum_{k=0}^{2}\binom{6}{2-k}\binom{8}{k}\right] \ | ||
+ | &=\binom{14}{0}+\binom{14}{4}+\left[\binom{14}{6}-1\right]+\binom{14}{2} \\ | ||
+ | &=1+1001+[3003-1]+91 \ | ||
+ | &=4095, | ||
+ | \end{align*}</cmath> | ||
+ | from which <math>N\equiv\boxed{\textbf{(D) } 95}\pmod{100}.</math> | ||
− | + | ~MRENTHUSIASM | |
− | ==Solution | + | ==Solution 3 (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>f(x,y)=\sum_{m=0}^8\sum_{n=0}^6 a_{mn}x^my^n,</cmath> |
− | <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 <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> |
− | f(x,y)=\sum_{m=0}^8\sum_{n=0}^6 a_{mn}x^my^n | + | 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>, then <cmath>h(i)+h(-1)+h(-i)+h(1)=1+1+1+1=4.</cmath> |
− | </cmath> | + | Otherwise, |
− | 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>h(i)+h(-1)+h(-i)+h(1)=0.</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> | ||
− | 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> | ||
− | h(i)+h(-1)+h(-i)+h(1)=1+1+1+1=4 | ||
− | </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 | ||
− | ==Solution | + | ==Solution 4 (Enumeration)== |
− | + | Note that <math>\binom{6}{t}\binom{8}{b}</math> different groups can be formed by selecting <math>t</math> tenors and <math>b</math> basses. By casework, we construct the following table: | |
<cmath>\begin{array}{c|c|c|c} | <cmath>\begin{array}{c|c|c|c} | ||
& & & \ [-2ex] | & & & \ [-2ex] | ||
− | \textbf{\# of Tenors} & \textbf{\# of Basses} & \textbf{\# of | + | \textbf{\# of Tenors} & \textbf{\# of Basses} & \textbf{\# of Groups} & \textbf{Evaluate \# of Groups} \ [0.5ex] |
\hline\hline | \hline\hline | ||
& & & \ [-2ex] | & & & \ [-2ex] | ||
− | 0 & | + | 0 & 4 & \tbinom{6}{0}\tbinom{8}{4} & 70 \ [1ex] |
− | + | 0 & 8 & \tbinom{6}{0}\tbinom{8}{8} & 1 \ [1ex] | |
− | + | \hline | |
− | + | & & & \ [-2ex] | |
− | + | 1 & 1 & \tbinom{6}{1}\tbinom{8}{1} & 48 \ [1ex] | |
− | + | 1 & 5 & \tbinom{6}{1}\tbinom{8}{5} & 336 \ [1ex] | |
− | |||
\hline | \hline | ||
& & & \ [-2ex] | & & & \ [-2ex] | ||
− | + | 2 & 2 & \tbinom{6}{2}\tbinom{8}{2} & 420 \ [1ex] | |
− | + | 2 & 6 & \tbinom{6}{2}\tbinom{8}{6} & 420 \ [1ex] | |
− | 2 & | ||
− | |||
− | |||
\hline | \hline | ||
& & & \ [-2ex] | & & & \ [-2ex] | ||
− | 4 & 0 & \tbinom{6}{4}\tbinom{8}{0} & \tbinom{6}{ | + | 3 & 3 & \tbinom{6}{3}\tbinom{8}{3} & 1120 \ [1ex] |
− | 5 & 1 & \tbinom{6}{5}\tbinom{8}{1} & \tbinom{6}{ | + | 3 & 7 & \tbinom{6}{3}\tbinom{8}{7} & 160 \ [1ex] |
− | 6 & 2 & \tbinom{6}{6}\tbinom{8}{2} & \tbinom{6}{ | + | \hline |
+ | & & & \ [-2ex] | ||
+ | 4 & 0 & \tbinom{6}{4}\tbinom{8}{0} & 15 \ [1ex] | ||
+ | 4 & 4 & \tbinom{6}{4}\tbinom{8}{4} & 1050 \ [1ex] | ||
+ | 4 & 8 & \tbinom{6}{4}\tbinom{8}{8} & 15 \ [1ex] | ||
+ | \hline | ||
+ | & & & \ [-2ex] | ||
+ | 5 & 1 & \tbinom{6}{5}\tbinom{8}{1} & 48 \ [1ex] | ||
+ | 5 & 5 & \tbinom{6}{5}\tbinom{8}{5} & 336 \ [1ex] | ||
+ | \hline | ||
+ | & & & \ [-2ex] | ||
+ | 6 & 2 & \tbinom{6}{6}\tbinom{8}{2} & 28 \ [1ex] | ||
+ | 6 & 6 & \tbinom{6}{6}\tbinom{8}{6} & 28 \ [1ex] | ||
\end{array}</cmath> | \end{array}</cmath> | ||
− | We | + | We find the total number of such groups: <cmath>N=70+1+48+336+420+420+1120+160+15+1050+15+48+336+28+28=4095,</cmath> |
− | <cmath> | + | from which <math>N\equiv\boxed{\textbf{(D) } 95}\pmod{100}.</math> |
− | N | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Alternatively, since the answer choices have different units digits, it suffices to find the units digit of <math>N</math> only. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ~sugar_rush ~MRENTHUSIASM | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ==Solution 5 (Symmetry Applied Twice)== | |
− | + | Consider the set of all <math>2^{8+6}=2^{14}</math> possible choirs that can be formed. For a given choir let <math>D</math> be the difference in the number of tenors and bases modulo <math>4</math>, so <math>D = T - B \pmod{4}.</math> Exactly half of all choirs have either <math>D=0</math> or <math>D=2</math>. To see this, pick one of the tenors and note that including or removing him from a choir changes <math>D</math> by <math>\pm1</math>. Of those <math>2^{13}</math> choirs with <math>D=0</math> or <math>D=2</math>, we claim exactly half have <math>D=0</math>. To see this, for any choir having <math>D=0</math> or <math>D=2</math>, we can replace the <math>T</math> tenors with the <math>6 - T</math> tenors who were not in the choir, thereby sending <math>D \mapsto D + 2 \pmod{4}.</math> Excluding the empty choir, there are <math>2^{12}-1 = 4095</math> choirs that meet the conditions of the problem, and the answer is <math>\boxed{\textbf{(D) } 95}</math>. | |
− | ~ | + | ~telluridetoaster and ~bigskystomper |
==Video Solution by Punxsutawney Phil== | ==Video Solution by Punxsutawney Phil== | ||
Line 114: | Line 109: | ||
https://www.youtube.com/watch?v=AjQARBvdZ20 | https://www.youtube.com/watch?v=AjQARBvdZ20 | ||
− | ==Video Solution by OmegaLearn ( | + | ==Video Solution by OmegaLearn (Using Vandermonde's Identity)== |
https://www.youtube.com/watch?v=mki7xtZLk1I | https://www.youtube.com/watch?v=mki7xtZLk1I | ||
Latest revision as of 04:40, 26 July 2024
Contents
[hide]- 1 Problem
- 2 Solution 1 (Bijection)
- 3 Solution 2 (Vandermonde's Identity)
- 4 Solution 3 (Generating Functions)
- 5 Solution 4 (Enumeration)
- 6 Solution 5 (Symmetry Applied Twice)
- 7 Video Solution by Punxsutawney Phil
- 8 Video Solution by Hawk Math
- 9 Video Solution by OmegaLearn (Using Vandermonde's Identity)
- 10 See also
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 (Bijection)
Suppose that tenors and basses are selected. The requirements are and
It follows that basses are not selected. Since the ordered pairs and the ordered pairs have one-to-one correspondence, we consider the ordered pairs instead. The requirements become and which simplify to and respectively.
As the total number of such groups is from which
~MRENTHUSIASM
Solution 2 (Vandermonde's Identity)
Suppose that tenors and basses are selected. The requirements are and
Note that different groups can be formed by selecting tenors and basses. Since we apply casework:
- If then different group can be formed.
- If then different groups can be formed.
- If then different groups can be formed, recalling that
- If then different groups can be formed.
By the combinatorial identity and Vandermonde's Identity we find the total number of such groups: from which
~MRENTHUSIASM
Solution 3 (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 , then 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 4 (Enumeration)
Note that different groups can be formed by selecting tenors and basses. By casework, we construct the following table: We find the total number of such groups: from which
Alternatively, since the answer choices have different units digits, it suffices to find the units digit of only.
~sugar_rush ~MRENTHUSIASM
Solution 5 (Symmetry Applied Twice)
Consider the set of all possible choirs that can be formed. For a given choir let be the difference in the number of tenors and bases modulo , so Exactly half of all choirs have either or . To see this, pick one of the tenors and note that including or removing him from a choir changes by . Of those choirs with or , we claim exactly half have . To see this, for any choir having or , we can replace the tenors with the tenors who were not in the choir, thereby sending Excluding the empty choir, there are choirs that meet the conditions of the problem, and the answer is .
~telluridetoaster and ~bigskystomper
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.