Difference between revisions of "2016 AMC 12B Problems/Problem 24"
(→Solution) |
m (→Solution) |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | =Problem= | + | ==Problem== |
There are exactly <math>77,000</math> ordered quadruplets <math>(a, b, c, d)</math> such that <math>\gcd(a, b, c, d) = 77</math> and <math>\operatorname{lcm}(a, b, c, d) = n</math>. What is the smallest possible value for <math>n</math>? | There are exactly <math>77,000</math> ordered quadruplets <math>(a, b, c, d)</math> such that <math>\gcd(a, b, c, d) = 77</math> and <math>\operatorname{lcm}(a, b, c, d) = n</math>. What is the smallest possible value for <math>n</math>? | ||
<math>\textbf{(A)}\ 13,860\qquad\textbf{(B)}\ 20,790\qquad\textbf{(C)}\ 21,560 \qquad\textbf{(D)}\ 27,720 \qquad\textbf{(E)}\ 41,580</math> | <math>\textbf{(A)}\ 13,860\qquad\textbf{(B)}\ 20,790\qquad\textbf{(C)}\ 21,560 \qquad\textbf{(D)}\ 27,720 \qquad\textbf{(E)}\ 41,580</math> | ||
− | =Solution= | + | ==Solution== |
− | Let <math>A=a | + | Let <math>A=\frac{a}{77},\ B=\frac{b}{77}</math>, etc., so that <math>\gcd(A,B,C,D)=1</math>. Then for each prime power <math>p^k</math> in the prime factorization of <math>N=\frac{n}{77}</math>, at least one of the prime factorizations of <math>(A,B,C,D)</math> has <math>p^k</math>, at least one has <math>p^0</math>, and all must have <math>p^m</math> with <math>0\le m\le k</math>. |
Let <math>f(k)</math> be the number of ordered quadruplets of integers <math>(m_1,m_2,m_3,m_4)</math> such that <math>0\le m_i\le k</math> for all <math>i</math>, the largest is <math>k</math>, and the smallest is <math>0</math>. Then for the prime factorization <math>N=2^{k_2}3^{k_3}5^{k_5}\ldots</math> we must have <math>77000=f(k_2)f(k_3)f(k_5)\ldots</math> So let's take a look at the function <math>f(k)</math> by counting the quadruplets we just mentioned. | Let <math>f(k)</math> be the number of ordered quadruplets of integers <math>(m_1,m_2,m_3,m_4)</math> such that <math>0\le m_i\le k</math> for all <math>i</math>, the largest is <math>k</math>, and the smallest is <math>0</math>. Then for the prime factorization <math>N=2^{k_2}3^{k_3}5^{k_5}\ldots</math> we must have <math>77000=f(k_2)f(k_3)f(k_5)\ldots</math> So let's take a look at the function <math>f(k)</math> by counting the quadruplets we just mentioned. | ||
− | There are <math>14</math> quadruplets which consist only of <math>0</math> and <math>k</math>. Then there are <math>36(k-1)</math> quadruplets which include three different values, and <math>12(k-1)(k-2)</math> with four. Thus <math>f(k)=14+12(k-1)(3+k-2)=14+12(k^2-1)</math> and the first few values from <math>k=1</math> onwards are <cmath>14,50,110,194,302,434,590,770,\ldots</cmath> Straight away we notice that <math>14\cdot 50\cdot 110=77000</math>, so the prime factorization of <math>N</math> can use the exponents <math>1,2,3</math>. To make it as small as possible, assign the larger exponents to smaller primes. The result is <math>N=2^33^25^1=360</math>, so <math>n=360\cdot 77=27720</math> which is answer <math>\textbf{(D)}</math>. | + | There are <math>14</math> quadruplets which consist only of <math>0</math> and <math>k</math>. Then there are <math>36(k-1)</math> quadruplets which include three different values, and <math>12(k-1)(k-2)</math> with four. Thus <math>f(k)=14+12(k-1)(3+k-2)=14+12(k^2-1)</math> and the first few values from <math>k=1</math> onwards are <cmath>14,50,110,194,302,434,590,770,\ldots</cmath> Straight away we notice that <math>14\cdot 50\cdot 110=77000</math>, so the prime factorization of <math>N</math> can use the exponents <math>1,2,3</math>. To make it as small as possible, assign the larger exponents to smaller primes. The result is <math>N=2^33^25^1=360</math>, so <math>n=360\cdot 77=27720</math> which is answer <math>\boxed{\textbf{(D)}}</math>. |
− | Also, to get the above formula of <math>f(k)=12 k^2+2</math>, we can also use the complementary counting by doing <math>(k+1)^4-k^4-k^4+(k-1)^4</math>, while the first term <math>(k+1)^4</math> is for the four integers to independently have k+1 choices each, with the second term indicating to subtract all the possibilities for the four integers to have values between 0 and k-1, and similarly the third term indicating to subtract all the possibilities for the four integers to have values between 1 and k, in the end the fourth term meaning the make up for the values between 1 and k-1. | + | Also, to get the above formula of <math>f(k)=12 k^2+2</math>, we can also use the complementary counting by doing <math>(k+1)^4-k^4-k^4+(k-1)^4</math>, while the first term <math>(k+1)^4</math> is for the four integers to independently have <math>k+1</math> choices each, with the second term indicating to subtract all the possibilities for the four integers to have values between <math>0</math> and <math>k-1</math>, and similarly the third term indicating to subtract all the possibilities for the four integers to have values between <math>1</math> and <math>k</math>, in the end the fourth term meaning the make up for the values between <math>1</math> and <math>k-1</math>. |
==See Also== | ==See Also== | ||
{{AMC12 box|year=2016|ab=B|num-a=25|num-b=23}} | {{AMC12 box|year=2016|ab=B|num-a=25|num-b=23}} | ||
+ | {{MAA Notice}} |
Latest revision as of 21:55, 24 December 2020
Problem
There are exactly ordered quadruplets
such that
and
. What is the smallest possible value for
?
Solution
Let , etc., so that
. Then for each prime power
in the prime factorization of
, at least one of the prime factorizations of
has
, at least one has
, and all must have
with
.
Let be the number of ordered quadruplets of integers
such that
for all
, the largest is
, and the smallest is
. Then for the prime factorization
we must have
So let's take a look at the function
by counting the quadruplets we just mentioned.
There are quadruplets which consist only of
and
. Then there are
quadruplets which include three different values, and
with four. Thus
and the first few values from
onwards are
Straight away we notice that
, so the prime factorization of
can use the exponents
. To make it as small as possible, assign the larger exponents to smaller primes. The result is
, so
which is answer
.
Also, to get the above formula of , we can also use the complementary counting by doing
, while the first term
is for the four integers to independently have
choices each, with the second term indicating to subtract all the possibilities for the four integers to have values between
and
, and similarly the third term indicating to subtract all the possibilities for the four integers to have values between
and
, in the end the fourth term meaning the make up for the values between
and
.
See Also
2016 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 23 |
Followed by Problem 25 |
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.