2020 AIME I Problem 7

Below is the professionally curated solution for Problem 7 of the 2020 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:combinationsVandermonde’s ConvolutionLegendre’s Formulaprime factorization

Difficulty rating: 2450

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.

Solution:

A committee with kk men has k+1k + 1 women, so N=k=011(11k)(12k+1)=k=011(11k)(1211k)=(2311)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} 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 6Full ExamProblem 8

Problem 7 in Other Years