Skip to main content

2019 AMC 12B Problem 14

Problem 14 of 25IntermediateNumber TheoryCounting & Probability

Let SS be the set of all positive integer divisors of 100,000.100{,}000. How many numbers are the product of two distinct elements of S?S?

Answer choices

Show solution

Solution

Since 100,000=2555,100{,}000=2^5\cdot5^5, every divisor is 2a5b2^a5^b with 0a,b5.0\le a,b\le5. A product of two divisors is 2x5y2^x5^y with 0x,y10,0\le x,y\le10, and every such pair (x,y)(x,y) is attainable, giving 1111=12111\cdot11=121 values. We need two distinct divisors. A value 2x5y2^x5^y is forced to be a divisor times itself only when both xx and yy have a unique split, which happens exactly when x,y{0,10}.x,y\in\{0,10\}. Those 44 corner values (1, 210, 510, 2105101,\ 2^{10},\ 5^{10},\ 2^{10}5^{10}) cannot use two distinct divisors. The count is 1214=117.121-4=117. Thus, C is the correct answer.

More practice

Concepts: factor · prime factorization · complementary counting

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.