2021 AMC 12A Problems/Problem 15
- 1 Problem
- 2 Solution 1 (Without Words)
- 3 Solution 2 (Generating Functions)
- 4 Solution 3 (Casework and Vandermonde's Identity)
- 5 Solution 4 (Combinatorial 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
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:
Solution 4 (Combinatorial 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 remaining to one valid group from the original
Clearly, the mapping is satisfied. For each group from the remaining 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.
The absolute difference becomes Since is even, we conclude that must also 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 also becomes This mapping is satisfied by Case 1.
Now, the proof of the bolded claim is complete.
Therefore, excluding the empty group gives
Video Solution by Punxsutawney Phil
Video Solution by Hawk Math
Video Solution by OmegaLearn (using Vandermonde's Identity)
|2021 AMC 12A (Problems • Answer Key • Resources)|
|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|