2019 AMC 10B Problems/Problem 19: Difference between revisions
Pinotation (talk | contribs) |
|||
| (9 intermediate revisions by 6 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 <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>. | 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>. | ||
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 | 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 \( 2^5 \times 5^5 \). We biject the question from "How many unique integers..." to, "How many possible units digits can occur", as the 36 factors will just branch from the units digits. (They also form a 1-1 correspondence). | |||
How? Well, you can imagine just the single factors of 10, that being, \( 2 \times 5 \). Then, We see that our factors are 1, 2, 5, or 10. Therefore, the product of two elements that may occur are 1x2, 2x5, 2x10, 5x1, 5x2, 5x10, 1, and 10 itself. These are 8 elements. The unique units digits of this are either 0 or 1. Then, we have the number of factors, that being, \( (1+1)(1+1) = 4 \). 4 multiplied by the two units digits reveals 8 as well. Notice that 100,000 | 10, and therefore there exists a 1-1 correspondence. If we wanted to count the distinct elements only, just subtract 1 and 10, or \( 2^0 \times 5^0 \) and \( 2 \times 5 \)! That easy! | |||
Continuing on, through inspection, the main multiples that may be formed are simply going to end in 0, \( 2^0 = 1 \), or \( 5^n \mod 10 \equiv 5 \). | |||
Then, we have a total of \( 36 \times 3 = 108 \) cases that may occur (number of factors times possible units digits given only the prime factorization). | |||
We now consider either one side is \( 2^n \times 5^0 \) or the other is \( 5^n \times 2^0 \) for \( 1 \le n \in \mathbb{Z} \le 5 \). Of course, the fact of \( 5^n \times 2^0 \) is always 5, so we only need to consider \( 2^n \times 5^0 \). This gives us either 2, 4, 8, or 6 as our units digits. However, one can quickly notice that 8 is already possible through 4 and 2 and because 6 represents 16, 16 is just \( 2 \times 8 \). Therefore, we only have 2 and 4 remaining. We distribute this to either the units digits 0, 1, and 5, giving us \( 3^2 = 9 \) total possibilities. | |||
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== | ==Video Solution by OmegaLearn== | ||
Latest revision as of 23:57, 22 October 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 
be the set of all positive integer divisors of 
How many numbers are the product of two distinct elements of 
Solution 1
The prime factorization of 
is 
. Thus, we choose two numbers 
and 
where 
and 
, whose product is 
, where 
and 
.
Notice that this is similar to choosing a divisor of 
, which has 
divisors. However, some of the divisors of 
cannot be written as a product of two distinct divisors of , namely: 
, , 
, and 
. The last two cannot be written because the maximum factor of containing only 
s or 
s (and not both) is only 
or 
. Since the factors chosen must be distinct, the last two numbers cannot be written because they would require 
or 
. The first two would require 
and 
, respectively. This gives 
candidate numbers. It is not too hard to show that every number of the form 
, where 
, and 
are not both 
or 
, can be written as a product of two distinct elements in . Hence the answer is 
.
~hashbrown2009 (revised and fully updated)
Solution 2
Set \( S \) has the number of factors in 100,000.
The prime factorization of 100,000 is \( 2^5 \times 5^5 \). We biject the question from "How many unique integers..." to, "How many possible units digits can occur", as the 36 factors will just branch from the units digits. (They also form a 1-1 correspondence).
How? Well, you can imagine just the single factors of 10, that being, \( 2 \times 5 \). Then, We see that our factors are 1, 2, 5, or 10. Therefore, the product of two elements that may occur are 1x2, 2x5, 2x10, 5x1, 5x2, 5x10, 1, and 10 itself. These are 8 elements. The unique units digits of this are either 0 or 1. Then, we have the number of factors, that being, \( (1+1)(1+1) = 4 \). 4 multiplied by the two units digits reveals 8 as well. Notice that 100,000 | 10, and therefore there exists a 1-1 correspondence. If we wanted to count the distinct elements only, just subtract 1 and 10, or \( 2^0 \times 5^0 \) and \( 2 \times 5 \)! That easy!
Continuing on, through inspection, the main multiples that may be formed are simply going to end in 0, \( 2^0 = 1 \), or \( 5^n \mod 10 \equiv 5 \).
Then, we have a total of \( 36 \times 3 = 108 \) cases that may occur (number of factors times possible units digits given only the prime factorization).
We now consider either one side is \( 2^n \times 5^0 \) or the other is \( 5^n \times 2^0 \) for \( 1 \le n \in \mathbb{Z} \le 5 \). Of course, the fact of \( 5^n \times 2^0 \) is always 5, so we only need to consider \( 2^n \times 5^0 \). This gives us either 2, 4, 8, or 6 as our units digits. However, one can quickly notice that 8 is already possible through 4 and 2 and because 6 represents 16, 16 is just \( 2 \times 8 \). Therefore, we only have 2 and 4 remaining. We distribute this to either the units digits 0, 1, and 5, giving us \( 3^2 = 9 \) total possibilities.
We add 108 and 9 to get \( 108 + 9 =\) .
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. Error creating thumbnail: File missing
