AMC 10 · 2019 · #19

Grade 6 arithmetic

divisor-countprime-factorizationcombinatorial-identityexponents complementary-countingidentify-subproblems ↑ Prerequisites: divisor-countprime-factorization

📏 Long solution 💡 4 insights

Problem

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

$\textbf{(A) }98\qquad\textbf{(B) }100\qquad\textbf{(C) }117\qquad\textbf{(D) }119\qquad\textbf{(E) }121$

Pick an answer.

(A)

(B)

100

(C)

117

(D)

119

(E)

121

View mode:

Toolkit + CCSS Solution

Understand

Restated: 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$?

Givens: $100{,}000 = 10^5 = 2^5 \cdot 5^5$; $S$ = set of all positive divisors of $100{,}000$; Each divisor has the form $2^a \cdot 5^b$ with $0 \le a \le 5$ and $0 \le b \le 5$; $|S| = 6 \cdot 6 = 36$; Choices: (A) $98$, (B) $100$, (C) $117$, (D) $119$, (E) $121$

Unknowns: The number of distinct values $d_1 \cdot d_2$ with $d_1, d_2 \in S$ and $d_1 \ne d_2$

Understand

Restated: 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$?

Plan

Primary tool: #16 Change Focus / Count the Complement

Secondary: #7 Identify Subproblems, #9 Solve an Easier Related Problem

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

Execute — Answer: C

#7 Identify Subproblems 6.NS.B.4 Step 1

Set up the candidate universe.
Each element of $S$ has the form $2^a \cdot 5^b$ with $0 \le a, b \le 5$.
A product of two elements has exponents $a_1 + a_2 \in [0, 10]$ and $b_1 + b_2 \in [0, 10]$.
So every product is a divisor of $2^{10} \cdot 5^{10}$, which has $(10+1)(10+1) = 121$ divisors.
These $121$ values are the *candidate* products.

$$\text{candidates} = 11 \cdot 11 = 121$$

💡 Products live in a $11 \times 11$ grid of $(a, b)$ exponent sums — start with the whole grid.

#9 Solve an Easier Related Problem 6.EE.B.6 Step 2

Now identify which candidates CANNOT be obtained from two *distinct* divisors.
A value $2^A \cdot 5^B$ comes from distinct $(a_1, b_1) \ne (a_2, b_2)$ with $a_1 + a_2 = A$, $b_1 + b_2 = B$, and each of $a_i, b_i$ in $[0, 5]$.
The constraint is: the chosen $(a_1, b_1)$ and $(a_2, b_2)$ must be different points in $[0, 5] \times [0, 5]$.

$$a_1 + a_2 = A,\;\; b_1 + b_2 = B,\;\; 0 \le a_i, b_i \le 5,\;\; (a_1,b_1) \ne (a_2,b_2)$$

💡 Translate "distinct divisors" to "distinct $(a, b)$ pairs".

#16 Change Focus / Count the Complement 6.EE.B.6 Step 3

Check $A = B = 0$, i.e., the candidate value $1$.
We need $a_1 + a_2 = 0$ and $b_1 + b_2 = 0$ with $a_i, b_i \ge 0$ — forces $a_1 = a_2 = b_1 = b_2 = 0$, so both divisors are $1$.
Not distinct.
So $1$ is unreachable.

$$2^0 \cdot 5^0 = 1 \;\;\text{(impossible — forces } (0,0) \cdot (0,0))$$

💡 Only way to multiply to $1$ is $1 \times 1$, but that's the same divisor twice.

#16 Change Focus / Count the Complement 6.EE.B.6 Step 4

Check $A = 10, B = 10$, candidate $2^{10} \cdot 5^{10} = 10^{10}$.
Need $a_1 + a_2 = 10$ with $a_i \le 5$, forcing $a_1 = a_2 = 5$; similarly $b_1 = b_2 = 5$.
So both divisors are $2^5 \cdot 5^5 = 100{,}000$.
Not distinct.
Unreachable.

$$2^{10} \cdot 5^{10} \;\;\text{(impossible — forces both} = 10^5)$$

💡 Top corner of the grid has only one factorization — twin divisors.

#16 Change Focus / Count the Complement 6.EE.B.6 Step 5

Check $A = 10, B = 0$, candidate $2^{10}$.
Need $a_1 + a_2 = 10$ with $a_i \le 5$, so $a_1 = a_2 = 5$.
And $b_1 + b_2 = 0$, so $b_1 = b_2 = 0$.
Both divisors $= 2^5 \cdot 5^0 = 32$.
Not distinct.
Unreachable.

$$2^{10} \;\;\text{(impossible — forces both} = 32)$$

💡 Same forced-pair trap, just on the $2$-axis.

#16 Change Focus / Count the Complement 6.EE.B.6 Step 6

Check $A = 0, B = 10$, candidate $5^{10}$.
Same forced pair: both divisors $= 5^5 = 3125$.
Not distinct.
Unreachable.

$$5^{10} \;\;\text{(impossible — forces both} = 3125)$$

💡 Mirror image of the previous case.

#9 Solve an Easier Related Problem 6.EE.B.6 Step 7

Verify every OTHER candidate IS reachable.
Take any $(A, B)$ in $[0, 10]^2$ not in the four bad corners.
Strategy: pick $a_1 = \min(A, 5)$ and adjust slightly to break a tie.
Concretely, for $(A, B) = (1, 0)$: $(a_1, b_1) = (0, 0), (a_2, b_2) = (1, 0)$ — distinct, both in range.
For $(A, B) = (5, 5)$: $(0, 0)$ and $(5, 5)$ — distinct.
For $(A, B) = (10, 5)$: forces $a_1 = a_2 = 5$, but $b_1 + b_2 = 5$ allows $b_1 = 0, b_2 = 5$ — distinct $(5, 0), (5, 5)$.
The only candidates with NO distinct-pair choice are the four corners $(0,0), (10,0), (0,10), (10,10)$ — because each forces both coordinates to their forced single value.

$$\text{bad} = \{(0,0), (10,0), (0,10), (10,10)\},\;\; |\text{bad}| = 4$$

💡 Force-the-pair fails only when BOTH coordinates have a unique factorization — and that's only at the four extreme corners.

#16 Change Focus / Count the Complement 4.OA.A.3 Step 8

Subtract: reachable $= 121 - 4 = 117$.
Answer: choice (C).

$$121 - 4 = \boxed{117}$$

💡 Universe minus exceptions — done.

[1] #7 6.NS.B.4 Set up the candidate universe. Each element of $S$ has the form $2^a \cdot 5^b$

[2] #9 6.EE.B.6 Now identify which candidates CANNOT be obtained from two *distinct* divisors. A

[3] #16 6.EE.B.6 Check $A = B = 0$, i.e., the candidate value $1$. We need $a_1 + a_2 = 0$ and $b

[4] #16 6.EE.B.6 Check $A = 10, B = 10$, candidate $2^{10} \cdot 5^{10} = 10^{10}$. Need $a_1 + a

[5] #16 6.EE.B.6 Check $A = 10, B = 0$, candidate $2^{10}$. Need $a_1 + a_2 = 10$ with $a_i \le 5

[6] #16 6.EE.B.6 Check $A = 0, B = 10$, candidate $5^{10}$. Same forced pair: both divisors $= 5^

[7] #9 6.EE.B.6 Verify every OTHER candidate IS reachable. Take any $(A, B)$ in $[0, 10]^2$ not

[8] #16 4.OA.A.3 Subtract: reachable $= 121 - 4 = 117$. Answer: choice (C).

Review

Reasonableness: $117$ is between choices $100$ and $119$, and exactly $121 - 4$, where $121$ is the count of divisors of $100{,}000^2$ and $4$ is the count of corners that need twin factorizations. Sanity check on a smaller case: divisors of $100 = 2^2 \cdot 5^2$ are $9$ in number; products of two distinct divisors live among divisors of $10^4$ ($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.

Alternative: Tool #2 (Systematic List): for each candidate $(A, B)$ in $[0, 10]^2$, count factorizations into two distinct elements of $S$. For most $(A, B)$ there are multiple, and we just need at least one — so the four-corner exception calculation is the cleanest. Direct enumeration without the complement is much slower.

CCSS standards used (min grade 6)

4.OA.A.3 Solve multi-step word problems using four operations with whole numbers (Final subtraction $121 - 4 = 117$.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Working with prime factorization $100{,}000 = 2^5 \cdot 5^5$ and counting divisors as $(5+1)(5+1)$.)
6.EE.B.6 Use variables to represent numbers and write expressions to solve problems (Writing divisors as $2^a \cdot 5^b$ and reducing the question to which $(A, B)$ exponent sums are reachable from distinct $(a_i, b_i)$ pairs.)

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

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 6)

More like this