Difference between revisions of "2019 AIME I Problems/Problem 7"
Thanosaops (talk | contribs) (→Solution) |
(→Solution 6 (Official MAA)) |
||
(35 intermediate revisions by 16 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>\log_{10} x + 2 \log_{10} (\gcd(x,y)) = 60 | + | There are positive integers <math>x</math> and <math>y</math> that satisfy the system of equations |
+ | <cmath> | ||
+ | \begin{align*} | ||
+ | \log_{10} x + 2 \log_{10} (\text{gcd}(x,y)) &= 60\\ | ||
+ | \log_{10} y + 2 \log_{10} (\text{lcm}(x,y)) &= 570. | ||
+ | \end{align*} | ||
+ | </cmath> | ||
+ | Let <math>m</math> be the number of (not necessarily distinct) prime factors in the prime factorization of <math>x</math>, and let <math>n</math> be the number of (not necessarily distinct) prime factors in the prime factorization of <math>y</math>. Find <math>3m+2n</math>. | ||
− | ==Solution== | + | ==Solution 1== |
− | Add the two equations to get that log x+log y+2(log(gcd(x,y))+log(lcm(x,y)))=630. | + | Add the two equations to get that <math>\log x+\log y+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630</math>. |
− | Then, use the theorem log a+log b=log ab to get the equation log xy+2(log(gcd(x,y))+log(lcm(x,y)))=630. | + | 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>. | |
− | This can easily be simplified to log xy=210, or xy = 10^210. | + | This can easily be simplified to <math>\log(xy)=210</math>, or <math>xy = 10^{210}</math>. |
− | 10^210 can be factored into 2^210 | + | |
− | Multiply by two to get 2m +2n, which is 840. | + | <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>. |
− | Then, use the first equation | + | Multiply by two to get <math>2m +2n</math>, which is <math>840</math>. |
− | Factor this into 2^20 | + | 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 you 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>. |
− | Add m to 2m + 2n (which is 840) to get 40+840 = 880. | + | 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 <math>840</math>) to get <math>40+840 = \boxed{880}</math>. | ||
+ | |||
+ | ==Solution 2 (Bashier Solution)== | ||
+ | |||
+ | First simplifying the first and second equations, we get that | ||
+ | |||
+ | <cmath>\log_{10}(x\cdot\text{gcd}(x,y)^2)=60</cmath> | ||
+ | <cmath>\log_{10}(y\cdot\text{lcm}(x,y)^2)=570</cmath> | ||
+ | |||
+ | |||
+ | Thus, when the two equations are added, we have that | ||
+ | <cmath>\log_{10}(x\cdot y\cdot\text{gcd}^2\cdot\text{lcm}^2)=630</cmath> | ||
+ | When simplified, this equals | ||
+ | <cmath>\log_{10}(x^3y^3)=630</cmath> | ||
+ | so this means that | ||
+ | <cmath>x^3y^3=10^{630}</cmath> | ||
+ | so | ||
+ | <cmath>xy=10^{210}.</cmath> | ||
+ | |||
+ | Now, the following cannot be done on a proof contest but let's (intuitively) assume that <math>x<y</math> and <math>x</math> and <math>y</math> are both powers of <math>10</math>. This means the first equation would simplify to <cmath>x^3=10^{60}</cmath> and <cmath>y^3=10^{570}.</cmath> Therefore, <math>x=10^{20}</math> and <math>y=10^{190}</math> and if we plug these values back, it works! <math>10^{20}</math> has <math>20\cdot2=40</math> total factors and <math>10^{190}</math> has <math>190\cdot2=380</math> so <cmath>3\cdot 40 + 2\cdot 380 = \boxed{880}.</cmath> | ||
+ | |||
+ | 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 <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 == | ||
+ | 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 | ||
+ | |||
+ | ==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> | ||
+ | |||
+ | ==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]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 18:01, 14 March 2021
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 you 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 .
Solution 2 (Bashier Solution)
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
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.