Difference between revisions of "2019 AIME I Problems/Problem 7"
(→Solution 4) |
Schintalpati (talk | contribs) (Solution 8) |
||
(30 intermediate revisions by 18 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
− | There are positive integers <math>x</math> and <math>y</math> that satisfy the system of equations <cmath> | + | There are positive integers <math>x</math> and <math>y</math> that satisfy the system of equations |
+ | <cmath> | ||
\begin{align*} | \begin{align*} | ||
\log_{10} x + 2 \log_{10} (\text{gcd}(x,y)) &= 60\\ | \log_{10} x + 2 \log_{10} (\text{gcd}(x,y)) &= 60\\ | ||
Line 9: | Line 10: | ||
==Solution 1== | ==Solution 1== | ||
− | Add the two equations to get that <math>\log x+\log y+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630</math>. | + | Add the two equations to get that <math>\log x+\log y+2(\log(\gcd(x,y))+2(\log(\text{lcm}(x,y)))=630</math>. |
Then, we use the theorem <math>\log a+\log b=\log ab</math> to get the equation, <math>\log (xy)+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630</math>. | Then, we use the theorem <math>\log a+\log b=\log ab</math> to get the equation, <math>\log (xy)+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630</math>. | ||
Using the theorem that <math>\gcd(x,y) \cdot \text{lcm}(x,y)=x\cdot y</math>, along with the previously mentioned theorem, we can get the equation <math>3\log(xy)=630</math>. | Using the theorem that <math>\gcd(x,y) \cdot \text{lcm}(x,y)=x\cdot y</math>, along with the previously mentioned theorem, we can get the equation <math>3\log(xy)=630</math>. | ||
This can easily be simplified to <math>\log(xy)=210</math>, or <math>xy = 10^{210}</math>. | This can easily be simplified to <math>\log(xy)=210</math>, or <math>xy = 10^{210}</math>. | ||
− | <math>10^{210}</math> can be factored into <math>2^{210} \cdot 5^{210}</math>, and <math>m+n</math> equals to the sum of the exponents of 2 and 5, which is <math>210+210 = 420</math>. | + | <math>10^{210}</math> can be factored into <math>2^{210} \cdot 5^{210}</math>, and <math>m+n</math> equals to the sum of the exponents of <math>2</math> and <math>5</math>, which is <math>210+210 = 420</math>. |
Multiply by two to get <math>2m +2n</math>, which is <math>840</math>. | Multiply by two to get <math>2m +2n</math>, which is <math>840</math>. | ||
− | Then, use the first equation (<math>\log x + 2\log(\gcd(x,y)) = 60</math>) to show that x has to have lower degrees of 2 and 5 than y. Therefore, | + | Then, use the first equation (<math>\log x + 2\log(\gcd(x,y)) = 60</math>) to show that <math>x</math> has to have lower degrees of <math>2</math> and <math>5</math> than <math>y</math> (you can also test when <math>x>y</math>, which is a contradiction to the restrains we set before). Therefore, <math>\gcd(x,y)=x</math>. Then, turn the equation into <math>3\log x = 60</math>, which yields <math>\log x = 20</math>, or <math>x = 10^{20}</math>. |
− | Factor this into <math>2^{20} \cdot 5^{20}</math>, and add the two 20's, resulting in m, which is 40. | + | Factor this into <math>2^{20} \cdot 5^{20}</math>, and add the two 20's, resulting in <math>m</math>, which is <math>40</math>. |
− | Add <math>m</math> to <math>2m + 2n</math> (which is 840) to get <math>40+840 = \boxed{880}</math>. | + | Add <math>m</math> to <math>2m + 2n</math> (which is <math>840</math>) to get <math>40+840 = \boxed{880}</math>. |
− | == | + | ~minor mistake fix by virjoy2001 |
+ | ~minor mistake fix by oralayhan | ||
+ | |||
+ | Remark: You can obtain the contradiction by using LTE. If <math>\nu_2{(x)}\geq{\nu_2{(y)}}, \nu_2{(y^2x)}=60</math>. However, <math>\nu_2{(xy)}=210</math> a contradiction. Same goes with taking <math>\nu_5{(x,y)}</math> | ||
+ | |||
+ | ===Easier Approach to Finish=== | ||
+ | After noting that <math>xy=10^{210},</math> notice that we can let <math>x=10^a</math> and <math>y=10^b.</math> Thus, we have from the given equations (1) and (2) respectively, that: | ||
+ | <cmath>a+2a=60</cmath> | ||
+ | <cmath>b+2b=570</cmath> | ||
+ | Solving, we get <math>(a,b)=(20,190).</math> This matches with our constraint that <math>xy=10^{210},</math> so we finish from here. | ||
+ | |||
+ | <math>x=2^{20}\cdot 5^{20}, y=2^{190}\cdot 5^{190}.</math> Thus, the answer desired is <math>3(20+20)+2(190+190)=880.</math> ~mathboy282 | ||
+ | |||
+ | ==Solution 2== | ||
First simplifying the first and second equations, we get that | First simplifying the first and second equations, we get that | ||
Line 43: | Line 57: | ||
==Solution 3 (Easy Solution)== | ==Solution 3 (Easy Solution)== | ||
Let <math>x=10^a</math> and <math>y=10^b</math> and <math>a<b</math>. Then the given equations become <math>3a=60</math> and <math>3b=570</math>. Therefore, <math>x=10^{20}=2^{20}\cdot5^{20}</math> and <math>y=10^{190}=2^{190}\cdot5^{190}</math>. Our answer is <math>3(20+20)+2(190+190)=\boxed{880}</math>. | Let <math>x=10^a</math> and <math>y=10^b</math> and <math>a<b</math>. Then the given equations become <math>3a=60</math> and <math>3b=570</math>. Therefore, <math>x=10^{20}=2^{20}\cdot5^{20}</math> and <math>y=10^{190}=2^{190}\cdot5^{190}</math>. Our answer is <math>3(20+20)+2(190+190)=\boxed{880}</math>. | ||
+ | |||
==Solution 4 == | ==Solution 4 == | ||
− | We will use the notation <math>(a, b)</math> for <math>\gcd(a, b)</math> and <math>[a, b]</math> as <math>\text{lcm}(a, b)</math> We can start a | + | We will use the notation <math>(a, b)</math> for <math>\gcd(a, b)</math> and <math>[a, b]</math> as <math>\text{lcm}(a, b)</math>. |
+ | We can start with a similar way to Solution 1. We have, by logarithm properties, <math>\log_{10}{x}+\log_{10}{(x, y)^2}=60</math> or <math>x(x, y)^2=10^{60}</math>. We can do something similar to the second equation and our two equations become <cmath>x(x, y)^2=10^{60}</cmath> <cmath>y[x, y]^2=10^{570}</cmath>Adding the two equations gives us <math>xy(x, y)^2[x, y]^2=10^{630}</math>. Since we know that <math>(a, b)\cdot[a, b]=ab</math>, <math>x^3y^3=10^{630}</math>, or <math>xy=10^{210}</math>. We can express <math>x</math> as <math>2^a5^b</math> and <math>y</math> as <math>2^c5^d</math>. Another way to express <math>(x, y)</math> is now <math>2^{min(a, c)}5^{min(b, d)}</math>, and <math>[x, y]</math> is now <math>2^{max(a, c)}5^{max(b, d)}</math>. We know that <math>x<y</math>, and thus, <math>a<c</math>, and <math>b<d</math>. Our equations for <math>lcm</math> and <math>gcd</math> now become <cmath>2^a5^b(2^a5^a)^2=10^{60}</cmath> or <math>a=b=20</math>. Doing the same for the <math>lcm</math> equation, we have <math>c=d=190</math>, and <math>190+20=210</math>, which satisfies <math>xy=210</math>. Thus, <math>3m+2n=3(20+20)+2(190+190)=\boxed{880}</math>. | ||
~awsomek | ~awsomek | ||
+ | |||
+ | ==Solution 5== | ||
+ | Let <math>x=d\alpha, y=d\beta, (\alpha, \beta)=1</math>. Simplifying, <math>d^3\alpha=10^{60}, d^3\alpha^2\beta^3=10^{510} \implies \alpha\beta^3 = 10^{510}=2^{510} \cdot 5^{510}</math>. Notice that since <math>\alpha, \beta</math> are coprime, and <math>\alpha < 5^{90}</math>(Prove it yourself !) , <math>\alpha=1, \beta = 10^{170}</math>. Hence, <math>x=10^{20}, y=10^{190}</math> giving the answer <math>\boxed{880}</math>. | ||
+ | |||
+ | (Solution by Prabh1512) | ||
+ | ==Solution 6 (Official MAA)== | ||
+ | The two equations are equivalent to <math>x(\gcd(x,y))^2=10^{60}</math> and <math>y(\operatorname{lcm}(x,y))^2=10^{570}</math> respectively. Multiplying corresponding sides of the equations leads to <math>xy(\gcd(x,y)\operatorname{lcm}(x,y))^2=(xy)^3=10^{630}</math>, so <math>xy=10^{210}</math>. It follows that there are nonnegative integers <math>a,\,b,\,c,</math> and <math>d</math> such that <math>(x,y)=(2^a5^b,2^c5^d)</math> with <math>a+c=b+d=210</math>. Furthermore, <cmath>\frac{(\operatorname{lcm}(x,y))^2}{x}=\frac{y(\operatorname{lcm}(x,y))^2}{xy}=\frac{10^{570}}{10^{210}}=10^{360}.</cmath> Thus <math>\max(2a,2c)-a=\max(2b,2d)-b=360.</math> Because neither <math>2a-a</math> nor <math>2b-b</math> can equal <math>360</math> when <math>a+c=b+d=210,</math> it follows that <math>2c-a=2d-b=360</math>. Hence <math>(a,b,c,d)=(20,20,190,190</math>, so the prime factorization of <math>x</math> has <math>20+20=40</math> prime factors, and the prime factorization of <math>y</math> has <math>190+190=380</math> prime factors. The requested sum is <math>3\cdot40+2\cdot380=880.</math> | ||
+ | |||
+ | ==Solution 7== | ||
+ | Add the two equations and use the fact that <math>\gcd\left(x,y\right)\cdot\mathrm{lcm}\left(x,y\right)=xy</math> to find that <math>xy=10^{210}</math>. So let <math>x=2^a5^b</math> and <math>y=2^{210-a}5^{210-b}</math> for <math>0\leq a,b\leq210</math>. If <math>a\geq105</math> then the exponent of <math>2</math> in <math>x\cdot\gcd\left(x,y\right)^2=10^{60}</math> is <math>a+2\left(210-a\right)=420-a</math>, so <math>a=360</math>, contradiction. So <math>a<105</math>. Then the exponent of <math>2</math> in <math>x\cdot\gcd\left(x,y\right)^2</math> is <math>a+2a=3a</math>, so <math>a=20</math>. Similarly, <math>b=20</math>. Then <math>3m+2n=3\left(a+b\right)+2\left(420-a-b\right)=\boxed{880}</math> as desired. | ||
+ | |||
+ | ~from trumpeter in the AoPS Forums Contest Discussion | ||
+ | |||
+ | ==Solution 8== | ||
+ | We can simplify the equations step by step. The first equation simplifies to <math>log(</math>(x)(<math>(gcd(x,y))^2</math>)<math>)=60</math>. The second equation simplifies to log(<math>(y)</math>(<math>(lcm(x,y)^2</math>)<math>)=570</math>. Up to here, we used the exponent and addition log identities. | ||
+ | |||
+ | Now before we move on to the next few simplification steps, we must remember that <math>gcd(a,b)</math>*<math>lcm(a,b)</math>=<math>a*b</math>. | ||
+ | |||
+ | Due to the fact that these log's are in base <math>10</math>, this makes the first and second equation equal to <math>10^{60}</math>, <math>10^{570}</math> respectively. In this step, we switched the log's into exponential form. Now we multiply both equations to get <math>x*y</math>*<math>(xy)^2</math>=(<math>x^3</math>)(<math>y^3</math>)=<math>10^{630}</math>. Now we take the cube root of both sides to get <math>xy=10^{210}</math>. | ||
+ | |||
+ | We've now gotten to the crucial part of this equation. Though this wouldn't pass for full points in a proof-based contest, this is AIME. So, we assume that <math>x<y</math>. We also let <math>x</math>=<math>10^a</math> and <math>y</math>=<math>10^b</math> That means that <math>gcd(x,y)</math> is <math>x</math> and the <math>lcm(x,y)</math> is <math>y</math> due to the fact that we are also assuming that both <math>x,y</math> are <math>10^a</math>, <math>10^b</math> respectively. | ||
+ | |||
+ | If we put our last few insights together into the first and second equation, we see that <math>x</math>=<math>10^{20}</math>. We also see that <math>y</math>=<math>10^{190}</math>. We could check these if wanted (don't worry they work), but if you were very limited on time for this question, just assume these values work and move on. | ||
+ | |||
+ | Now <math>10^{20}</math> factors as <math>2^{20}</math>*<math>5^{20}</math>. This has <math>40</math> prime factors. <math>2</math>, <math>20</math> times and <math>5</math>, <math>20</math> times. <math>10^{190}</math> factors as <math>2^{190}</math>*<math>5^{190}</math>. This has <math>380</math> prime factors. <math>2</math>, <math>190</math> times and <math>5</math>, <math>190</math> times. Now it's just <math>40*3+380*2=880</math> as our final answer. | ||
+ | |||
+ | -Schintalpati | ||
+ | |||
+ | ==Video Solution(Pretty Straightforward) == | ||
+ | https://www.youtube.com/watch?v=NOLk9-A4eDo | ||
+ | Remember to subscribe! | ||
+ | |||
+ | ~North America math Contest Go Go Go | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2019|n=I|num-b=6|num-a=8}} | {{AIME box|year=2019|n=I|num-b=6|num-a=8}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | [[Category:Intermediate Algebra Problems]] | ||
+ | |||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 17:48, 20 July 2024
Contents
Problem
There are positive integers and
that satisfy the system of equations
Let
be the number of (not necessarily distinct) prime factors in the prime factorization of
, and let
be the number of (not necessarily distinct) prime factors in the prime factorization of
. Find
.
Solution 1
Add the two equations to get that .
Then, we use the theorem
to get the equation,
.
Using the theorem that
, along with the previously mentioned theorem, we can get the equation
.
This can easily be simplified to
, or
.
can be factored into
, and
equals to the sum of the exponents of
and
, which is
.
Multiply by two to get
, which is
.
Then, use the first equation (
) to show that
has to have lower degrees of
and
than
(you can also test when
, which is a contradiction to the restrains we set before). Therefore,
. Then, turn the equation into
, which yields
, or
.
Factor this into
, and add the two 20's, resulting in
, which is
.
Add
to
(which is
) to get
.
~minor mistake fix by virjoy2001 ~minor mistake fix by oralayhan
Remark: You can obtain the contradiction by using LTE. If . However,
a contradiction. Same goes with taking
Easier Approach to Finish
After noting that notice that we can let
and
Thus, we have from the given equations (1) and (2) respectively, that:
Solving, we get
This matches with our constraint that
so we finish from here.
Thus, the answer desired is
~mathboy282
Solution 2
First simplifying the first and second equations, we get that
Thus, when the two equations are added, we have that
When simplified, this equals
so this means that
so
Now, the following cannot be done on a proof contest but let's (intuitively) assume that and
and
are both powers of
. This means the first equation would simplify to
and
Therefore,
and
and if we plug these values back, it works!
has
total factors and
has
so
Please remember that you should only assume on these math contests because they are timed; this would technically not be a valid solution.
Solution 3 (Easy Solution)
Let and
and
. Then the given equations become
and
. Therefore,
and
. Our answer is
.
Solution 4
We will use the notation for
and
as
.
We can start with a similar way to Solution 1. We have, by logarithm properties,
or
. We can do something similar to the second equation and our two equations become
Adding the two equations gives us
. Since we know that
,
, or
. We can express
as
and
as
. Another way to express
is now
, and
is now
. We know that
, and thus,
, and
. Our equations for
and
now become
or
. Doing the same for the
equation, we have
, and
, which satisfies
. Thus,
.
~awsomek
Solution 5
Let . Simplifying,
. Notice that since
are coprime, and
(Prove it yourself !) ,
. Hence,
giving the answer
.
(Solution by Prabh1512)
Solution 6 (Official MAA)
The two equations are equivalent to and
respectively. Multiplying corresponding sides of the equations leads to
, so
. It follows that there are nonnegative integers
and
such that
with
. Furthermore,
Thus
Because neither
nor
can equal
when
it follows that
. Hence
, so the prime factorization of
has
prime factors, and the prime factorization of
has
prime factors. The requested sum is
Solution 7
Add the two equations and use the fact that to find that
. So let
and
for
. If
then the exponent of
in
is
, so
, contradiction. So
. Then the exponent of
in
is
, so
. Similarly,
. Then
as desired.
~from trumpeter in the AoPS Forums Contest Discussion
Solution 8
We can simplify the equations step by step. The first equation simplifies to (x)(
)
. The second equation simplifies to log(
(
)
. Up to here, we used the exponent and addition log identities.
Now before we move on to the next few simplification steps, we must remember that *
=
.
Due to the fact that these log's are in base, this makes the first and second equation equal to
,
respectively. In this step, we switched the log's into exponential form. Now we multiply both equations to get
*
=(
)(
)=
. Now we take the cube root of both sides to get
.
We've now gotten to the crucial part of this equation. Though this wouldn't pass for full points in a proof-based contest, this is AIME. So, we assume that . We also let
=
and
=
That means that
is
and the
is
due to the fact that we are also assuming that both
are
,
respectively.
If we put our last few insights together into the first and second equation, we see that =
. We also see that
=
. We could check these if wanted (don't worry they work), but if you were very limited on time for this question, just assume these values work and move on.
Now factors as
*
. This has
prime factors.
,
times and
,
times.
factors as
*
. This has
prime factors.
,
times and
,
times. Now it's just
as our final answer.
-Schintalpati
Video Solution(Pretty Straightforward)
https://www.youtube.com/watch?v=NOLk9-A4eDo Remember to subscribe!
~North America math Contest Go Go Go
See Also
2019 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.