Difference between revisions of "2021 AMC 12A Problems/Problem 15"
MRENTHUSIASM (talk | contribs) m (→Solution 3 (Casework and Vandermonde's Identity)) |
MRENTHUSIASM (talk | contribs) (→Solution 4 (Combinatoric Argument): Changed some grammar and organization.) |
||
Line 87: | Line 87: | ||
First, we set one tenor and one bass aside. We argue that each group from the <math>12</math> remaining singers (of any size, including <math>0</math>) corresponds to exactly one valid group from the original <math>14</math> singers. | First, we set one tenor and one bass aside. We argue that each group from the <math>12</math> remaining singers (of any size, including <math>0</math>) corresponds to exactly one valid group from the original <math>14</math> singers. | ||
− | The <math>12</math> remaining singers can form <cmath>2^{12}=\sum_ | + | The <math>12</math> remaining singers can form <cmath>2^{12}=\left[\sum_{t=0}^{5}\binom5t\right]\cdot\left[\sum_{b=0}^{7}\binom7b\right]</cmath> groups. The left side counts directly, while the right side uses casework (selecting <math>t</math> tenors and <math>b</math> basses for each group). Now, we map each group from the <math>12</math> to one valid group from the original <math>14.</math> |
By casework: | By casework: | ||
Line 95: | Line 95: | ||
Clearly, the mapping is satisfied. For each group from the <math>12,</math> we can obtain one valid group from the original <math>14</math> by adding one tenor or one bass accordingly. | Clearly, the mapping is satisfied. For each group from the <math>12,</math> we can obtain one valid group from the original <math>14</math> by adding one tenor or one bass accordingly. | ||
<li><math>|b-t|\equiv0\pmod{4}</math></li><p> | <li><math>|b-t|\equiv0\pmod{4}</math></li><p> | ||
− | Since <math>\binom7b=\binom{7}{7-b},</math> we can select <math>7-b</math> basses instead of <math>b</math> basses, without changing the number of groups. Therefore, we have the absolute difference <math>\left|(7-b)-t\right|=\left|7-(b+t)\right|.</math> Since <math>b\equiv t\pmod{4},</math> we conclude that <math>\left|7-(b+t)\right|\equiv 1\text{ or }3\pmod{4} | + | Since <math>\binom7b=\binom{7}{7-b},</math> we can select <math>7-b</math> basses instead of <math>b</math> basses, without changing the number of groups. Therefore, we have the absolute difference <math>\left|(7-b)-t\right|=\left|7-(b+t)\right|.</math> Since <math>b\equiv t\pmod{4},</math> we conclude that <math>b=t</math> must be even. It follows that <math>\left|(7-b)-t\right|=\left|7-(b+t)\right|\equiv 1\text{ or }3\pmod{4}.</math> This mapping is satisfied by Case 1. |
<li><math>|b-t|\equiv2\pmod{4}</math></li><p> | <li><math>|b-t|\equiv2\pmod{4}</math></li><p> | ||
− | By the same reasoning as Case 2, we select <math>7-b</math> basses instead of <math>b</math> basses. The absolute difference also | + | By the same reasoning as Case 2, we select <math>7-b</math> basses instead of <math>b</math> basses. The absolute difference is also <math>\left|7-(b+t)\right|.</math> Since <math>b-t</math> is even, we conclude that <math>b+t</math> must also be even. It follows that <math>\left|7-(b+t)\right|\equiv 1\text{ or }3\pmod{4}.</math> This mapping is satisfied by Case 1. |
</ol> | </ol> | ||
Revision as of 13:06, 11 May 2021
Contents
- 1 Problem
- 2 Solution 1 (Without Words)
- 3 Solution 2 (Generating Functions)
- 4 Solution 3 (Casework and Vandermonde's Identity)
- 5 Solution 4 (Combinatoric Argument)
- 6 Video Solution by Punxsutawney Phil
- 7 Video Solution by Hawk Math
- 8 Video Solution by OmegaLearn (using Vandermonde's Identity)
- 9 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 (Without Words)
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
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
Solution 4 (Combinatoric Argument)
We claim that if the empty group is allowed, then there are valid ways to choose the singers.
First, we set one tenor and one bass aside. We argue that each group from the remaining singers (of any size, including
) corresponds to exactly one valid group from the original
singers.
The remaining singers can form
groups. The left side counts directly, while the right side uses casework (selecting
tenors and
basses for each group). Now, we map each group from the
to one valid group from the original
By casework:
Clearly, the mapping is satisfied. For each group from the we can obtain one valid group from the original
by adding one tenor or one bass accordingly.
Since we can select
basses instead of
basses, without changing the number of groups. Therefore, we have the absolute difference
Since
we conclude that
must be even. It follows that
This mapping is satisfied by Case 1.
By the same reasoning as Case 2, we select basses instead of
basses. The absolute difference is also
Since
is even, we conclude that
must also be even. It follows that
This mapping is satisfied by Case 1.
Now, the proof of the bolded claim is complete.
Therefore, excluding the empty group gives
~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.