1991 AIME Problem 5

Attempt Problem 5 of the 1991 AIME 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 1991 AIME solutions, or check the answer key.

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

5.

Given a rational number, write it as a fraction in lowest terms and calculate the product of the resulting numerator and denominator. For how many rational numbers between 00 and 11 will 20!20! be the resulting product?

Answer: 128
Concepts:prime factorizationgreatest common divisorsubsets
Difficulty rating: 2250
Small Hint:

If ab\frac{a}{b} is in lowest terms and ab=20!ab=20!, each full prime power of 20!20! must go entirely to one of aa or bb

Big Hint:

Count ordered allocations of the distinct prime-power factors, then use the condition a<ba<b

Solution:

The distinct primes dividing 20!20! are 2,2, 3,3, 5,5, 7,7, 11,11, 13,13, 17,17, and 19.19. If ab\frac{a}{b} is in lowest terms and ab=20!,ab=20!, the entire power of each of these eight primes must be assigned to either aa or b.b. Thus there are 282^8 ordered coprime factorizations ab=20!.ab=20!. Since ab,a\neq b, exactly half have 0<ab<1.0<\frac{a}{b}<1. The number sought is 27=128.2^7=128.

← Problem 4#4
Full Exam

Problem 5 in Other Years