AMC 10 · 2019 · #19

Grade 6 arithmetic

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)

(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

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

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

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

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

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

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

5¹⁰ (impossible — forces both = 3125)

7STEP 7

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 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).

More like this