2020 AIME I Problems/Problem 7
A club consisting of men and women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as member or as many as members. Let be the number of such committees that can be formed. Find the sum of the prime numbers that divide
We will be selecting women, but not selecting men. We claim that the amount of women selected and the amount of men not selected adds to . This is easy to see: if women were chosen, then . Therefore, we simply take . ~awang11's sol
Solution 2 (Bash)
We casework on the amount of men on the committee.
If there are no men in the committee, there are ways to pick the women on the committee, for a total of . Notice that is equal to , so the case where no men are picked can be grouped with the case where all men are picked. When all men are picked, all females must also be picked, for a total of . Therefore, these cases can be combined to Since , and , we can further simplify this to
All other cases proceed similarly. For example, the case with one men or ten men is equal to . Now, if we factor out a , then all cases except the first two have a factor of , so we can factor this out too to make our computation slightly easier. The first two cases (with factored out) give , and the rest gives . Adding the gives . Now, we can test for prime factors. We know there is a factor of , and the rest is . We can also factor out a , for , and the rest is . Adding up all the prime factors gives .
(Solves using both methods - Casework and Vandermonde's Identity)
Solution 3 (Vandermonde's identity)
Applying Vandermonde's identity by setting , , and , we obtain . ~Lcz
Consider the following setup: The dots to the left represent the men, and the dots to the right represent the women. Now, suppose we put a mark on people (the ). Those to the left of the dashed line get to be "in" on the committee if they have a mark. Those on the right side of the dashed line are already on the committee, but if they're marked they get forcibly evicted from it. If there were people marked on the left, there ends up being people not marked on the right. Circles represent those in the committee.
We have our bijection, so the number of ways will be .
Notice that the committee can consist of boys and girls. Summing over all possible gives Using the identity , and Pascal's Identity , we get Using the identity , this simplifies to so the desired answer is ~ktong
|2020 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|