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 "2017 AMC 12B Problems/Problem 16"

(→‎Solution)
(→‎Solution)
Line 6: Line 6:
 
==Solution==
 
==Solution==
  
−
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 <math>60,000</math>. If we divide this product by the exponent of <math>2</math> plus <math>1</math>, then we should get the number of odd factors. Then, the fraction of odd divisors over total divisors is <math>\dfrac{1}{e_2+1}</math> if <math>e_2</math> is the exponent of <math>2</math>. We can find <math>e_2</math> easily using Legendre's, so our final answer is <math>\dfrac{1}{10 + 5 + 3 + 1} = \boxed{\text{(B)} \dfrac{1}{19}}.</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 we divide this product by the exponent of <math>2</math> plus <math>1</math>, then we should get the number of odd factors. Then, the fraction of odd divisors over total divisors is <math>\dfrac{1}{e_2+1}</math> if <math>e_2</math> is the exponent of <math>2</math>. We can find <math>e_2</math> easily using Legendre's, so our final answer is <math>\dfrac{1}{10 + 5 + 3 + 1} = \boxed{\text{(B)} \dfrac{1}{19}}.</math>
  
 
~ icecreamrolls8
 
~ icecreamrolls8

Revision as of 20:28, 31 October 2022

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

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 we divide this product by the exponent of $2$ plus $1$, then we should get the number of odd factors. Then, the fraction of odd divisors over total divisors is $\dfrac{1}{e_2+1}$ if $e_2$ is the exponent of $2$. We can find $e_2$ easily using Legendre's, so our final answer is $\dfrac{1}{10 + 5 + 3 + 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 (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_12B_Problems/Problem_16&oldid=179877"