Competition · AMC preparation · step 4 of 4

AMC 10 · 2019B · #19

Grade 6 number-theory
Archetype Overlap / Complement Counting └ Sub-archetype Complement by Subtracting Forbidden Arrangements
divisor-countprime-factorizationcombinatorial-identityexponents complementary-countingidentify-subproblems ↑ Prerequisites: divisor-countprime-factorization
📏 Long solution 💡 4 insights
Problem
Let S be the set of all positive divisors of 100,000. How many distinct numbers can be written as the product of two distinct elements of S?

Pick an answer.

(A)
98
(B)
100
(C)
117
(D)
119
(E)
121

AMC 10 2019 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Change Focus / Count the Complement

Tool #16 (Complement): list ALL candidate values (divisors of 10¹⁰, which is 11 · 11 = 121) and subtract the few that cannot be written as a product of two distinct divisors of 10⁵. Tool #7 (Subproblems): a product of two divisors has the form 2^a · 5^b with 0 ≤ a, b ≤ 10 — so the question splits into "which (a, b) pairs are reachable?" Tool #9 (Easier Problem): the same kind of question on 100 = 2² · 5² first, then generalize.

1STEP 1

Count all the candidates

Every divisor of 100,000 is 2^a · 5^b (0 ≤ a, b ≤ 5), so each product divides 2¹⁰ · 5¹⁰ — 121 candidate values.

candidates = 11 · 11 = 121
2STEP 2

Look for unreachable candidates

So 2^A · 5^B is reachable only when A, B split as a₁+a₂, b₁+b₂ using two different points (a₁,b₁) ≠ (a₂,b₂), each coordinate in [0, 5].

a₁ + a₂ = A, b₁ + b₂ = B, 0 ≤ a_i, b_i ≤ 5, (a₁,b₁) ≠ (a₂,b₂)
3STEP 3

Check the candidate 1

Candidate 1 needs A = B = 0, forcing both divisors to equal 1 — the same divisor twice, so it's unreachable.

2⁰ · 5⁰ = 1 (impossible — forces (0,0) · (0,0))
4STEP 4

Check 10 to the tenth

Candidate 2¹⁰ · 5¹⁰ = 10¹⁰ forces a₁ = a₂ = 5 and b₁ = b₂ = 5 — both divisors are 100,000, so it's unreachable.

2¹⁰ · 5¹⁰ (impossible — forces both = 10⁵)
5STEP 5

Check 2 to the tenth

Candidate 2¹⁰ forces a₁ = a₂ = 5 and b₁ = b₂ = 0 — both divisors are 32, so it's unreachable.

2¹⁰ (impossible — forces both = 32)
6STEP 6

Check 5 to the tenth

Candidate 5¹⁰ is the mirror image — both divisors forced to 3,125, so it's unreachable.

5¹⁰ (impossible — forces both = 3125)
7STEP 7

Confirm the rest are reachable

Every other (A, B) has a valid distinct pair (e.g. (10, 5) gives (5,0) and (5,5)), so exactly 4 corner candidates are impossible.

bad = {(0,0), (10,0), (0,10), (10,10)}, |bad| = 4
8STEP 8

Subtract the bad cases

Subtract the impossible corners: 121 - 4 = 117. The answer is (C).

121 - 4 = 117
Answer
117
117 is between choices 100 and 119, and exactly 121 - 4, where 121 is the count of divisors of 100,000² and 4 is the count of corners that need twin factorizations. Sanity check on a smaller case: divisors of 100 = 2² · 5² are 9 in number; products of two distinct divisors live among divisors of 10⁴ (25 candidates); bad corners are the same four ((0,0), (4,0), (0,4), (4,4)); so the answer for 100 would be 25 - 4 = 21, which matches a direct enumeration.
💡Key takeaway

This AMC 10 problem only needs Grade 6 prime-factorization reasoning you already know — every divisor of 10⁵ is 2^a · 5^b, so products live among the 121 divisors of 10¹⁰, and only 4 "corner" values fail the distinct-pair rule. 121 - 4 = 117. The answer is (C).

  • Count all the candidates
  • Look for unreachable candidates
  • Check the candidate 1
  • Check 10 to the tenth
  • Check 2 to the tenth
  • Check 5 to the tenth
  • Confirm the rest are reachable
  • Subtract the bad cases

A parent dashboard for the family lives at sensimlab.com.

More like this

Same problem type. Tags show what each one shares with this problem.