2020 AIME I Problem 7

Attempt Problem 7 of the 2020 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2020 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

7.

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

Answer: 81
Concepts:combinationsVandermonde’s ConvolutionLegendre’s Formulaprime factorization
Difficulty rating: 2450
Solution:

A committee with kk men has k+1k + 1 women, so N=k=011(11k)(12k+1)=k=011(11k)(1211k)=(2311) \begin{aligned} N &= \sum_{k=0}^{11} \binom{11}{k}\binom{12}{k+1} \\ &= \sum_{k=0}^{11} \binom{11}{k}\binom{12}{11-k} \\ &= \binom{23}{11} \end{aligned} by Vandermonde's identity (both sides count ways to choose 1111 people from all 2323).

Now factor (2311)=23!11!12!.\binom{23}{11} = \frac{23!}{11!\,12!}. The primes 13,13, 17,17, 19,19, 2323 each appear in the numerator but not the denominator. By Legendre's formula the exponent of 22 is 19810=1,19 - 8 - 10 = 1, of 33 is 945=0,9 - 4 - 5 = 0, of 55 is 422=0,4 - 2 - 2 = 0, of 77 is 311=1,3 - 1 - 1 = 1, and of 1111 is 211=0.2 - 1 - 1 = 0. Hence N=2713171923.N = 2 \cdot 7 \cdot 13 \cdot 17 \cdot 19 \cdot 23.

The sum of the primes dividing NN is 2+7+13+17+19+23=81.2 + 7 + 13 + 17 + 19 + 23 = 81.

← Problem 6#6
Full Exam

Problem 7 in Other Years