2020 AIME I Problems/Problem 7
Contents
[hide]Problem
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
Solution 1
Let be the number of women selected. Then, the number of men not selected is
.
Note that the sum of the number of women selected and the number of men not selected is constant at
. Each combination of women selected and men not selected corresponds to a committee selection. Since choosing 12 individuals from the total of 23 would give
women and
men, the number of committee selections is
.
The answer is
.
~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 women 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
.
Video Solution:
https://youtu.be/MVxsY8DwHVk ~ avn
Solution 3 (Vandermonde's identity)
Applying [1] by setting ,
, and
, we obtain
.
~Lcz
Short Proof
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 .
~programjames1
Solution 4
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
Solution 5 (Official MAA)
Select any club members. That group will have
men and
women, so the number of women in the club not selected in that group is
. Thus, if the committee includes the men who were selected and the women who were not selected, the committee would have the correct number of men and women. Conversely, for every committee that could be formed with
men and
women, the men on this committee together with the women not on the committee comprise a subset of
club members. Thus
The requested sum is
Solution 6
Notice that if men are picked, then
women must be picked. Furthermore,
can range from
to
. Then,
Since
, this equals
According to Vandermonde's Identity,
~sid2012
Solution 7 (Recursion)
Test the cases where there are men
woman,
man
women,
men
women ... you will get the sequence
,
,
,
. Multiply all these numbers by
to get
,
,
,
, which is also
,
,
,
. Thus, continuing this pattern, the case with
men and
women should have
ways to select the committee.
(someone prove this rigorously im too lazy )
-Kevin2010
Video Solution by OmegaLearn
https://youtu.be/pGkLAX381_s?t=684
~ pi_is_3.14
Video Solution
(Solves using both methods - Casework and Vandermonde's Identity)
Video Solution
https://www.youtube.com/watch?v=fxlQMiElGFk&list=PLLCzevlMcsWN9y8YI4KNPZlhdsjPTlRrb&index=6 ~ MathEx
See Also
2020 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.