Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 AMC 10B Problems/Problem 19"

(removed solution 1 which was extremely similar to solution 2)
(→‎Solution)
 
(29 intermediate revisions by 19 users not shown)
Line 6: Line 6:
 
<math>\textbf{(A) }98\qquad\textbf{(B) }100\qquad\textbf{(C) }117\qquad\textbf{(D) }119\qquad\textbf{(E) }121</math>
 
<math>\textbf{(A) }98\qquad\textbf{(B) }100\qquad\textbf{(C) }117\qquad\textbf{(D) }119\qquad\textbf{(E) }121</math>
  
−
==Solution==
+
==Solution 1==
  
−
The prime factorization of 100,000 is <math>2^5 \cdot 5^5</math>. Thus, we choose two numbers <math>2^a5^b</math> and <math>2^c5^d</math> where <math>0 \le a,b,c,d \le 5</math> and <math>(a,b) \neq (c,d)</math>, whose product is <math>2^{a+c}5^{b+d}</math>, where <math>0 \le a+c \le 10</math> and <math>0 \le b+d \le 10</math>.
+
The prime factorization of <math>100,000</math> is <math>2^5 \cdot 5^5</math>. Thus, we choose two numbers <math>2^a5^b</math> and <math>2^c5^d</math> where <math>0 \le a,b,c,d \le 5</math> and <math>(a,b) \neq (c,d)</math>, whose product is <math>2^{a+c}5^{b+d}</math>, where <math>0 \le a+c \le 10</math> and <math>0 \le b+d \le 10</math>.
  
−
Consider <math>100000^2 = 2^{10}5^{10}</math>. The number of divisors is <math>(10+1)(10+1) = 121</math>. However, some of the divisors of <math>2^{10}5^{10}</math> cannot be written as a product of two distinct divisors of <math>2^5 \cdot 5^5</math>, namely: <math>1 = 2^05^0</math>, <math>2^{10}5^{10}</math>, <math>2^{10}</math>, and <math>5^{10}</math>. The last two can not be created because the maximum factor of 100,000 involving only 2s or 5s is only <math>2^5</math> or <math>5^5</math>. Since the factors chosen must be distinct, the last two numbers cannot be created because those require <math>2^5 \cdot 2^5</math> or <math>5^5 \cdot 5^5</math>. This gives <math>121-4 = 117</math> candidate numbers. It is not too hard to show that every number of the form <math>2^p5^q</math> where <math>0 \le p, q \le 10</math>, and <math>p,q</math> are not both 0 or 10, can be written as a product of two distinct elements in <math>S</math>. Hence the answer is <math>\boxed{\textbf{(C) } 117}</math>.
+
Notice that this is similar to choosing a divisor of <math>100,000^2 = 2^{10}5^{10}</math>, which has <math>(10+1)(10+1) = 121</math> divisors. However, some of the divisors of <math>2^{10}5^{10}</math> cannot be written as a product of two distinct divisors of <math>2^5 \cdot 5^5</math>, namely: <math>1 = 2^05^0</math>, <math>2^{10}5^{10}</math>, <math>2^{10}</math>, and <math>5^{10}</math>. The last two cannot be written because the maximum factor of <math>100,000</math> containing only <math>2</math>s or <math>5</math>s (and not both) is only <math>2^5</math> or <math>5^5</math>. Since the factors chosen must be distinct, the last two numbers cannot be written because they would require <math>2^5 \cdot 2^5</math> or <math>5^5 \cdot 5^5</math>. The first two would require <math>1 \cdot 1</math> and <math>2^{5}5^{5} \cdot 2^{5}5^{5}</math>, respectively. This gives <math>121-4 = 117</math> candidate numbers. It is not too hard to show that every number of the form <math>2^p5^q</math>, where <math>0 \le p, q \le 10</math>, and <math>p,q</math> are not both <math>0</math> or <math>10</math>, can be written as a product of two distinct elements in <math>S</math>. Hence the answer is <math>\boxed{\textbf{(C) } 117}</math>.
 +
 
 +
~hashbrown2009 (revised and fully updated)
 +
 
 +
==Solution 2==
 +
 
 +
Set \( S \) has the number of factors in 100,000. The prime factorization of 100,000 is
 +
<cmath>
 +
100,000 = 2^5 \times 5^5
 +
</cmath>
 +
Therefore set \( S \) has 36 elements.
 +
 
 +
Now, notice how \( 5^n \) will always end in 5, and \( 2^n \) will end in 2, 4, 8, or 6. We also include \( 2^0 \), and we see the unique units digits include 0, 1, 2, 4, 5, 6, and 8. However, most of the multiples of these numbers cannot divide 100,000, so we cancel out most of them and see that most units digits will end in 0, 1, and 5.
 +
 
 +
So we multiply the elements in \( S \) by 3, to get \( 36 \times 3 = 108 \).
 +
 
 +
We have 3 units digits that we can distribute to either the factors \( 2^0 \) or \( 2^n \). We can't distribute anything to \( 5^n \) because no matter what we multiply the units digits by, we always result in a units digits of 5, which we already considered. Therefore the number of ways to do this is \( 3^2 = 9 \).
 +
 
 +
We add 108 and 9 to get \( 108 + 9 =\) <math>\boxed{\textbf{(C) } 117}</math>.
 +
 
 +
This problem was much harder than anticipated.
 +
 
 +
~Pinotation
 +
 
 +
==Video Solution by OmegaLearn==
 +
https://youtu.be/ZhAZ1oPe5Ds?t=3975
 +
 
 +
~ pi_is_3.14
  
 
==See Also==
 
==See Also==
Line 16: Line 43:
 
{{AMC12 box|year=2019|ab=B|num-b=13|num-a=15}}
 
{{AMC12 box|year=2019|ab=B|num-b=13|num-a=15}}
 
{{MAA Notice}}
 
{{MAA Notice}}
−
SUB2PEWDS
 

Latest revision as of 17:09, 3 September 2025

The following problem is from both the 2019 AMC 10B #19 and 2019 AMC 12B #14, so both problems redirect to this page.

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$

Solution 1

The prime factorization of $100,000$ is $2^5 \cdot 5^5$. Thus, we choose two numbers $2^a5^b$ and $2^c5^d$ where $0 \le a,b,c,d \le 5$ and $(a,b) \neq (c,d)$, whose product is $2^{a+c}5^{b+d}$, where $0 \le a+c \le 10$ and $0 \le b+d \le 10$.

Notice that this is similar to choosing a divisor of $100,000^2 = 2^{10}5^{10}$, which has $(10+1)(10+1) = 121$ divisors. However, some of the divisors of $2^{10}5^{10}$ cannot be written as a product of two distinct divisors of $2^5 \cdot 5^5$, namely: $1 = 2^05^0$, $2^{10}5^{10}$, $2^{10}$, and $5^{10}$. The last two cannot be written because the maximum factor of $100,000$ containing only $2$s or $5$s (and not both) is only $2^5$ or $5^5$. Since the factors chosen must be distinct, the last two numbers cannot be written because they would require $2^5 \cdot 2^5$ or $5^5 \cdot 5^5$. The first two would require $1 \cdot 1$ and $2^{5}5^{5} \cdot 2^{5}5^{5}$, respectively. This gives $121-4 = 117$ candidate numbers. It is not too hard to show that every number of the form $2^p5^q$, where $0 \le p, q \le 10$, and $p,q$ are not both $0$ or $10$, can be written as a product of two distinct elements in $S$. Hence the answer is $\boxed{\textbf{(C) } 117}$.

~hashbrown2009 (revised and fully updated)

Solution 2

Set \( S \) has the number of factors in 100,000. The prime factorization of 100,000 is \[100,000 = 2^5 \times 5^5\] Therefore set \( S \) has 36 elements.

Now, notice how \( 5^n \) will always end in 5, and \( 2^n \) will end in 2, 4, 8, or 6. We also include \( 2^0 \), and we see the unique units digits include 0, 1, 2, 4, 5, 6, and 8. However, most of the multiples of these numbers cannot divide 100,000, so we cancel out most of them and see that most units digits will end in 0, 1, and 5.

So we multiply the elements in \( S \) by 3, to get \( 36 \times 3 = 108 \).

We have 3 units digits that we can distribute to either the factors \( 2^0 \) or \( 2^n \). We can't distribute anything to \( 5^n \) because no matter what we multiply the units digits by, we always result in a units digits of 5, which we already considered. Therefore the number of ways to do this is \( 3^2 = 9 \).

We add 108 and 9 to get \( 108 + 9 =\) $\boxed{\textbf{(C) } 117}$.

This problem was much harder than anticipated.

~Pinotation

Video Solution by OmegaLearn

https://youtu.be/ZhAZ1oPe5Ds?t=3975

~ pi_is_3.14

See Also

2019 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 18 		Followed by
Problem 20
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2019 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10B_Problems/Problem_19&oldid=259685"