Difference between revisions of "2017 AMC 12B Problems/Problem 16"

m (Solution)
(Solution)
 
(22 intermediate revisions by 12 users not shown)
Line 1: Line 1:
==Problem 16==
+
==Problem==
 
The number <math>21!=51,090,942,171,709,440,000</math> has over <math>60,000</math> positive integer divisors. One of them is chosen at random. What is the probability that it is odd?
 
The number <math>21!=51,090,942,171,709,440,000</math> has over <math>60,000</math> positive integer divisors. One of them is chosen at random. What is the probability that it is odd?
  
 
<math>\textbf{(A)}\ \frac{1}{21} \qquad \textbf{(B)}\ \frac{1}{19} \qquad \textbf{(C)}\ \frac{1}{18} \qquad \textbf{(D)}\ \frac{1}{2} \qquad \textbf{(E)}\ \frac{11}{21}</math>
 
<math>\textbf{(A)}\ \frac{1}{21} \qquad \textbf{(B)}\ \frac{1}{19} \qquad \textbf{(C)}\ \frac{1}{18} \qquad \textbf{(D)}\ \frac{1}{2} \qquad \textbf{(E)}\ \frac{11}{21}</math>
 +
 +
==Solution 1==
 +
 +
We can consider a factor of <math>21!</math> to be odd if it does not contain a <math>2</math>; hence, finding the exponent of <math>2</math> in the prime factorization of <math>21!</math> will help us find our answer. We can start off with all multiples of <math>2</math> up to <math>21</math>, which is <math>10</math>. Then, we find multiples of <math>4</math>, which is <math>5</math>. Next, we look at multiples of <math>8</math>, of which there are <math>2</math>. Finally, we know there is only one multiple of <math>16</math> in the set of positive integers up to <math>21</math>. Now, we can add all of these to get <math>10+5+2+1=18</math>. We know that, in the prime factorization of <math>21!</math>, we have <math>2^{18}</math>, and the only way to have an odd number is if there is not a <math>2</math> in that number's prime factorization. This only happens with <math>2^{0}</math>, which is only one of the 19 different exponents of 2 we could have (of which having each exponent is equally likely). Hence, we have  <math>\boxed{\text{(B)} \dfrac{1}{19}}.</math>
 +
 +
Solution by: armang32324
  
 
==Solution==
 
==Solution==
If a factor of <math>21!</math> is odd, that means it contains no factors of <math>2</math>. We can find the number of factors of two in <math>21!</math> by counting the number multiples of <math>2</math>, <math>4</math>, <math>8</math>, and <math>16</math> that are less than or equal to <math>21</math>.After some quick counting we find that this number is <math>10+5+2+1 = 18</math>. If the prime factorization of <math>21!</math> has <math>18</math> factors of <math>2</math>, there are <math>19</math> choices for each divisor for how many factors of <math>2</math> should be included (<math>0</math> to <math>18</math> inclusive). The probability that a randomly chosen factor is odd is the same as if the number of factors of <math>2</math> is <math>0</math> which is <math>\frac{1}{19} \Rightarrow \boxed{(B)}</math>.
+
 
 +
If <math>21!</math> prime factorizes into <math>p</math> prime factors with exponents <math>e_1</math> through <math>e_k</math>, then the product of the sums of each of these exponents plus <math>1</math> should be over <math>60,000</math>. If <math>e_2</math> is the exponent of <math>2</math> in the prime factorization of 21!, then we can find the number of odd factors of <math>21!</math> by dividing the total by <math>e_2+1</math>. Then, the number of odd divisors over total divisors is <math>\dfrac{1}{e_2+1}</math>. We can find <math>e_2</math> easily using Legendre's, so our final answer is <math>\dfrac{1}{10 + 5 + 2 + 1+1} = \boxed{\text{(B)} \dfrac{1}{19}}.</math>
 +
 
 +
~ icecreamrolls8
 +
 
 +
==Solution==
 +
If a factor of <math>21!</math> is odd, that means it contains no factors of <math>2</math>. We can find the number of factors of two in <math>21!</math> by counting the number multiples of <math>2</math>, <math>4</math>, <math>8</math>, and <math>16</math> that are less than or equal to <math>21</math> (Legendre's Formula). After some quick counting we find that this number is <math>10+5+2+1 = 18</math>. If the prime factorization of <math>21!</math> has <math>18</math> factors of <math>2</math>, there are <math>19</math> choices for each divisor for how many factors of <math>2</math> should be included (<math>0</math> to <math>18</math> inclusive). The probability that a randomly chosen factor is odd is the same as if the number of factors of <math>2</math> is <math>0</math> which is     <math>\boxed{\textbf{(B)}\frac{1}{19}}</math>.
  
 
Solution by: vedadehhc
 
Solution by: vedadehhc
 +
 +
==Solution 2==
 +
We can write <math>21!</math> as its prime factorization:
 +
<cmath>21!=2^{18}\times3^9\times5^4\times7^3\times11\times13\times17\times19</cmath>
 +
 +
Each exponent of these prime numbers are one less than the number of factors at play here. This makes sense; <math>2^{18}</math> is going to have <math>19</math> factors: <math>2^0, 2^1, 2^2,...\text{ }2^{18}</math>, and the other exponents will behave identically.
 +
 +
In other words, <math>21!</math> has <math>(18+1)(9+1)(4+1)(3+1)(1+1)(1+1)(1+1)(1+1)</math> factors.
 +
 +
We are looking for the probability that a randomly chosen factor of <math>21!</math> will be odd--numbers that do not contain multiples of <math>2</math> as factors.
 +
 +
From our earlier observation, the only factors of <math>21!</math> that are even are ones with at least one multiplier of <math>2</math>, so our probability of finding an odd factor becomes the following:
 +
<cmath>P(\text{odd})=\dfrac{\text{number of odd factors}}{\text{number of all factors}}=\dfrac{(9+1)(4+1)(3+1)(1+1)(1+1)(1+1)(1+1)}{(18+1)(9+1)(4+1)(3+1)(1+1)(1+1)(1+1)(1+1)}=\dfrac{1}{(18+1)}=\boxed{\dfrac{1}{19}}</cmath>
 +
 +
Solution submitted by [[User:TrueshotBarrage|David Kim]]
 +
 +
==Video Solution==
 +
 +
https://youtu.be/ZLHNTSIcGM8
 +
 +
-MistyMathMusic
 +
 +
==See Also==
 +
{{AMC12 box|year=2017|ab=B|num-b=15|num-a=17}}
 +
{{MAA Notice}}
 +
 +
[[Category:Introductory Combinatorics Problems]]
 +
[[Category:Introductory Probability Problems]]

Latest revision as of 13:55, 10 July 2023

Problem

The number $21!=51,090,942,171,709,440,000$ has over $60,000$ positive integer divisors. One of them is chosen at random. What is the probability that it is odd?

$\textbf{(A)}\ \frac{1}{21} \qquad \textbf{(B)}\ \frac{1}{19} \qquad \textbf{(C)}\ \frac{1}{18} \qquad \textbf{(D)}\ \frac{1}{2} \qquad \textbf{(E)}\ \frac{11}{21}$

Solution 1

We can consider a factor of $21!$ to be odd if it does not contain a $2$; hence, finding the exponent of $2$ in the prime factorization of $21!$ will help us find our answer. We can start off with all multiples of $2$ up to $21$, which is $10$. Then, we find multiples of $4$, which is $5$. Next, we look at multiples of $8$, of which there are $2$. Finally, we know there is only one multiple of $16$ in the set of positive integers up to $21$. Now, we can add all of these to get $10+5+2+1=18$. We know that, in the prime factorization of $21!$, we have $2^{18}$, and the only way to have an odd number is if there is not a $2$ in that number's prime factorization. This only happens with $2^{0}$, which is only one of the 19 different exponents of 2 we could have (of which having each exponent is equally likely). Hence, we have $\boxed{\text{(B)} \dfrac{1}{19}}.$

Solution by: armang32324

Solution

If $21!$ prime factorizes into $p$ prime factors with exponents $e_1$ through $e_k$, then the product of the sums of each of these exponents plus $1$ should be over $60,000$. If $e_2$ is the exponent of $2$ in the prime factorization of 21!, then we can find the number of odd factors of $21!$ by dividing the total by $e_2+1$. Then, the number of odd divisors over total divisors is $\dfrac{1}{e_2+1}$. We can find $e_2$ easily using Legendre's, so our final answer is $\dfrac{1}{10 + 5 + 2 + 1+1} = \boxed{\text{(B)} \dfrac{1}{19}}.$

~ icecreamrolls8

Solution

If a factor of $21!$ is odd, that means it contains no factors of $2$. We can find the number of factors of two in $21!$ by counting the number multiples of $2$, $4$, $8$, and $16$ that are less than or equal to $21$ (Legendre's Formula). After some quick counting we find that this number is $10+5+2+1 = 18$. If the prime factorization of $21!$ has $18$ factors of $2$, there are $19$ choices for each divisor for how many factors of $2$ should be included ($0$ to $18$ inclusive). The probability that a randomly chosen factor is odd is the same as if the number of factors of $2$ is $0$ which is $\boxed{\textbf{(B)}\frac{1}{19}}$.

Solution by: vedadehhc

Solution 2

We can write $21!$ as its prime factorization: \[21!=2^{18}\times3^9\times5^4\times7^3\times11\times13\times17\times19\]

Each exponent of these prime numbers are one less than the number of factors at play here. This makes sense; $2^{18}$ is going to have $19$ factors: $2^0, 2^1, 2^2,...\text{ }2^{18}$, and the other exponents will behave identically.

In other words, $21!$ has $(18+1)(9+1)(4+1)(3+1)(1+1)(1+1)(1+1)(1+1)$ factors.

We are looking for the probability that a randomly chosen factor of $21!$ will be odd--numbers that do not contain multiples of $2$ as factors.

From our earlier observation, the only factors of $21!$ that are even are ones with at least one multiplier of $2$, so our probability of finding an odd factor becomes the following: \[P(\text{odd})=\dfrac{\text{number of odd factors}}{\text{number of all factors}}=\dfrac{(9+1)(4+1)(3+1)(1+1)(1+1)(1+1)(1+1)}{(18+1)(9+1)(4+1)(3+1)(1+1)(1+1)(1+1)(1+1)}=\dfrac{1}{(18+1)}=\boxed{\dfrac{1}{19}}\]

Solution submitted by David Kim

Video Solution

https://youtu.be/ZLHNTSIcGM8

-MistyMathMusic

See Also

2017 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 15
Followed by
Problem 17
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png