Difference between revisions of "2020 AIME I Problems/Problem 7"

Revision as of 00:10, 13 March 2020

Problem

A club consisting of $11$ men and $12$ 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 $1$ member or as many as $23$ members. Let $N$ be the number of such committees that can be formed. Find the sum of the prime numbers that divide $N.$

Solution 1

We will be selecting girls, but not selecting boys. We claim that the amount of girls selected and the amount of guys not selected adds to $12$ . This is easy to see: if $k$ women were chosen, then $k + (11 - k + 1) = 12$ . Therefore, we simply take $\binom{23}{12} \implies \boxed{081}$ . ~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 $\dbinom{12}{1}$ ways to pick the women on the committee, for a total of $\dbinom{11}{0} \cdot \dbinom{12}{1}$ . Notice that $\dbinom{11}{0}$ is equal to $\dbinom{11}{11}$ , 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 $\dbinom{12}{12}$ . Therefore, these cases can be combined to $\dbinom{11}{0} \cdot (\dbinom{12}{1} + \dbinom{12}{12})$ Since $\dbinom{12}{12} = \dbinom{12}{0}$ , and $\dbinom{12}{0} + \dbinom{12}{1} = \dbinom{13}{1}$ , we can further simplify this to $\dbinom{11}{0} \cdot \dbinom{13}{1}$

All other cases proceed similarly. For example, the case with one men or ten men is equal to $\dbinom{11}{1} \cdot \dbinom{13}{2}$ . Now, if we factor out a $13$ , then all cases except the first two have a factor of $121$ , so we can factor this out too to make our computation slightly easier. The first two cases (with $13$ factored out) give $1+66=67$ , and the rest gives $121(10+75+270+504) = 103,939$ . Adding the $67$ gives $104,006$ . Now, we can test for prime factors. We know there is a factor of $2$ , and the rest is $52,003$ . We can also factor out a $7$ , for $7,429$ , and the rest is $17 \cdot 19 \cdot 23$ . Adding up all the prime factors gives $2+7+13+17+19+23 = \boxed{081}$ .

Solution 3 (Vandermonde's identity)

Applying Vandermonde's identity by setting $m=12$ , $n=11$ , and $r=11$ , we obtain $\binom{23}{11}\implies$ $\boxed{081}$ . ~Lcz

Solution 4

Notice that the committee can consist of $k$ boys and $k+1$ girls. Summing over all possible $k$ gives $\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{11}{0}\binom{12}{1}+\binom{11}{1}\binom{12}{2}+\cdots + \binom{11}{11}\binom{12}{12}$ Using the identity $\binom{n}{k}=\binom{n}{n-k}$ , and Pascal's Identity $\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$ , we get $\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{12}{12}+\binom{12}{1}\left(\binom{11}{0}+\binom{11}{1}\right)+\cdots$ $=\binom{12}{0}^2+\binom{12}{1}^2+\binom{12}{2}^2+\binom{12}{3}^2+\binom{12}{4}^2+\binom{12}{5}^2+\frac{\binom{12}{6}^2}{2}$ $=\frac{1}{2}\sum_{k=0}^{12}\binom{12}{k}^2$ Using the identity $\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}$ , this simplifies to $\frac{1}{2}\cdot \binom{24}{12}=\frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13}{2\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2}=2\cdot 7\cdot 13\cdot 17\cdot 19\cdot 23$ so the desired answer is $2+7+13+17+19+23=\boxed{081}$

@@ Line 17: / Line 17: @@
 Applying Vandermonde's identity by setting <math>m=12</math>, <math>n=11</math>, and <math>r=11</math>, we obtain <math>\binom{23}{11}\implies</math> <math>\boxed{081}</math>.
 ~Lcz
+== Solution 4 ==
+Notice that the committee can consist of <math>k</math> boys and <math>k+1</math> girls. Summing over all possible <math>k</math> gives
+<cmath>\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{11}{0}\binom{12}{1}+\binom{11}{1}\binom{12}{2}+\cdots + \binom{11}{11}\binom{12}{12}</cmath>
+Using the identity <math>\binom{n}{k}=\binom{n}{n-k}</math>, and Pascal's Identity <math>\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}</math>, we get
+<cmath>\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{12}{12}+\binom{12}{1}\left(\binom{11}{0}+\binom{11}{1}\right)+\cdots </cmath>
+<cmath>=\binom{12}{0}^2+\binom{12}{1}^2+\binom{12}{2}^2+\binom{12}{3}^2+\binom{12}{4}^2+\binom{12}{5}^2+\frac{\binom{12}{6}^2}{2}</cmath>
+<cmath>=\frac{1}{2}\sum_{k=0}^{12}\binom{12}{k}^2</cmath>
+Using the identity <math>\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}</math>, this simplifies to
+<cmath>\frac{1}{2}\cdot \binom{24}{12}=\frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13}{2\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2}=2\cdot 7\cdot 13\cdot 17\cdot 19\cdot 23</cmath>
+so the desired answer is <math>2+7+13+17+19+23=\boxed{081}</math>
 ==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

Page

Toolbox

Search