AMC 10 Step by Step
Log inSign up

2020 AMC 10A Problem 15

P11-15~4 minPrint
Divisibility & FactorsNumber PropertiesBasic ProbabilitySet up the equation/formula and compute; no special trick needed

A positive integer divisor of 12!12! is chosen at random. The probability that the divisor chosen is a perfect square can be expressed as mn\frac{m}{n} , where mm and nn are relatively prime positive integers. What is m+nm+n ?

Log in to save your progress.
Show solution without answering

Key insight

Write 12! as prime powers. A divisor chooses a power of each prime, and it is a square exactly when every chosen power is even.

Solution

Divisors are easiest to count once the number is broken into primes, so start there.

1. How many 2s are in 12!12!? Among 11 to 1212: six numbers are even (2,4,…,122, 4, \ldots, 12), giving one 22 each. Three of them (4,8,124, 8, 12) are multiples of 44 and give an extra 22. One (88) is a multiple of 88 and gives one more. Total 6+3+1=106 + 3 + 1 = 10.
2. The other primes. Multiples of 33: 3,6,9,123, 6, 9, 12 give 44 threes, and 99 gives one extra, so 55. Multiples of 55: 5,105, 10, so 22. Then 77 and 1111 appear once each. So
12!=210⋅35⋅52⋅7⋅11.12! = 2^{10} \cdot 3^{5} \cdot 5^{2} \cdot 7 \cdot 11.
3. Count all divisors. A divisor uses 22 between 00 and 1010 times (1111 choices), 33 between 00 and 55 times (66 choices), 55 between 00 and 22 times (33 choices), and 77 and 1111 each 00 or 11 times (22 choices each):
11×6×3×2×2=792.11 \times 6 \times 3 \times 2 \times 2 = 792.
4. Count square divisors. A number is a perfect square when every prime appears an even number of times. The even choices are: for 22, the powers 0,2,4,6,8,100, 2, 4, 6, 8, 10 (six); for 33, 0,2,40, 2, 4 (three); for 55, 0,20, 2 (two); for 77 and 1111, only 00 (one each):
6×3×2×1×1=36.6 \times 3 \times 2 \times 1 \times 1 = 36.
5. Probability. 36792=122\frac{36}{792} = \frac{1}{22}. So m=1m = 1, n=22n = 22, and m+n=23m + n = 23.

The answer is (E) 23\boxed{\textbf{(E)}\ 23}.

Why this works

Once a number is written as a product of prime powers, each divisor is just a choice of how many times to use each prime. Any rule about divisors that can be checked prime by prime (like "every power is even" for squares) is counted by multiplying the number of allowed choices for each prime.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

First factor 12!12!. The exponent of 22 is ⌊12/2⌋+⌊12/4⌋+⌊12/8⌋=6+3+1=10\lfloor 12/2 \rfloor + \lfloor 12/4 \rfloor + \lfloor 12/8 \rfloor = 6 + 3 + 1 = 10; of 33 it is 4+1=54 + 1 = 5; of 55 it is 22; and 77, 1111 appear once each:
12!=210⋅35⋅52⋅7⋅11.12! = 2^{10} \cdot 3^5 \cdot 5^2 \cdot 7 \cdot 11.

A divisor picks an exponent for each prime from 00 up to the exponent in 12!12!, so the number of divisors is
11⋅6⋅3⋅2⋅2=792.11 \cdot 6 \cdot 3 \cdot 2 \cdot 2 = 792.

A divisor is a perfect square exactly when every exponent it picks is even. The even choices are 0,2,…,100,2,\dots,10 for 22 (six), 0,2,40,2,4 for 33 (three), 0,20,2 for 55 (two), and only 00 for 77 and 1111:
6⋅3⋅2⋅1⋅1=36.6 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 36.

The probability is 36792=122\frac{36}{792} = \frac{1}{22}, so m+n=1+22=23m + n = 1 + 22 = 23.

The answer is (E) 23\boxed{\textbf{(E)}\ 23}.

Review in the AoPS books

Similar problems

Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.