Difference between revisions of "2017 USAJMO Problems/Problem 2"
(Adds another solution) |
Cocohearts (talk | contribs) (→Solution 1) |
||
(11 intermediate revisions by 6 users not shown) | |||
Line 7: | Line 7: | ||
(b) Describe all pairs <math>(x,y)</math> of positive integers satisfying the equation. | (b) Describe all pairs <math>(x,y)</math> of positive integers satisfying the equation. | ||
− | ==Solution 1 | + | ==Solution 1== |
− | We have <math>(3x^3+xy^2)(yx^2+3y^3)=(x-y)^7</math>, which can be expressed as <math>xy(3x^2+y^2)(x^2+3y^2)=(x-y)^7</math>. At this point, we think of substitution. A substitution of form <math>a=x+y, b=x-y</math> is slightly derailed by the leftover x and y terms, so instead, seeing the xy in front, we substitute <math>x=a+b, y=a-b</math>. This leaves us with <math>(a^2-b^2)(4a^2+4ab+4b^2)(4a^2-4ab+4b^2)=128b^7</math>, so <math>(a^2-b^2)(a^2+ab+b^2)(a^2-ab+b^2)=8b^7</math>. Expanding yields <math>a^6-b^6=8b^7</math>. Rearranging, we have <math>b^6(8b+1)=a^6</math>. To satisfy this equation in integers, <math>8b+1</math> must obviously be a <math>6th</math> power, and further inspection shows that it must also be odd. Also, since it is a square and all odd squares are 1 mod 8, every odd sixth power gives a solution. Since the problem asks for positive integers, the pair <math>(a,b)=(0,0)</math> does not work. We go to the next highest odd <math>6th</math> power, <math>3^6</math> or <math>729</math>. In this case, <math>b=91</math>, so the LHS is <math>91^6 | + | We have <math>(3x^3+xy^2)(yx^2+3y^3)=(x-y)^7</math>, which can be expressed as <math>xy(3x^2+y^2)(x^2+3y^2)=(x-y)^7</math>. At this point, we |
− | + | ||
+ | think of substitution. A substitution of form <math>a=x+y, b=x-y</math> is slightly derailed by the leftover x and y terms, so | ||
+ | |||
+ | instead, seeing the xy in front, we substitute <math>x=a+b, y=a-b</math>. This leaves us with <math>(a^2-b^2)(4a^2+4ab+4b^2)(4a^2- | ||
+ | 4ab+4b^2)=128b^7</math>, so <math>(a^2-b^2)(a^2+ab+b^2)(a^2-ab+b^2)=8b^7</math>. Expanding yields <math>a^6-b^6=8b^7</math>. Rearranging, we have | ||
+ | |||
+ | <math>b^6(8b+1)=a^6</math>. To satisfy this equation in integers, <math>8b+1</math> must obviously be a <math>6th</math> power, and further inspection shows | ||
+ | |||
+ | that it must also be odd. Also, since it is a square and all odd squares are 1 mod 8, every odd sixth power gives a | ||
+ | |||
+ | solution. Since the problem asks for positive integers, the pair <math>(a,b)=(0,0)</math> does not work. We go to the next highest odd | ||
+ | |||
+ | <math>6th</math> power, <math>3^6</math> or <math>729</math>. In this case, <math>b=91</math>, so the LHS is <math>91^6\cdot3^6=273^6</math>, so <math>a=273</math>. Using the original | ||
+ | |||
+ | substitution yields <math>(x,y)=(364,182)</math> as the first solution. We have shown part a by showing that there are an infinite | ||
+ | |||
+ | number of positive integer solutions for <math>(a,b)</math>, which can then be manipulated into solutions for <math>(x,y)</math>. To solve part | ||
+ | |||
+ | b, we look back at the original method of generating solutions. Define <math>a_n</math> and <math>b_n</math> to be the pair representing the nth | ||
+ | |||
+ | solution. Since the nth odd number is <math>2n+1</math>, <math>b_n=\frac{(2n+1)^6-1}{8}</math>. It follows that <math>a_n=(2n+1)b_n=\frac{(2n+1)^7- | ||
+ | (2n+1)}{8}</math>. From our original substitution, <math>(x,y)=\left(\frac{(2n+1)^7+(2n+1)^6-2n-2}{8}, \frac{(2n+1)^7-(2n+1)^6-2n} | ||
+ | {8}\right)</math>. | ||
==Solution 2 (and motivation)== | ==Solution 2 (and motivation)== | ||
Line 23: | Line 45: | ||
Now, we have that <cmath>\frac{(x+y)^6-(x-y)^6}{4}=(x-y)^7</cmath> | Now, we have that <cmath>\frac{(x+y)^6-(x-y)^6}{4}=(x-y)^7</cmath> | ||
Rearranging and getting rid of the denominator, we have that <cmath>(x+y)^6=4(x-y)^7+(x-y)^6</cmath> | Rearranging and getting rid of the denominator, we have that <cmath>(x+y)^6=4(x-y)^7+(x-y)^6</cmath> | ||
− | Factoring, we have <cmath>(x+y)^6=(x-y)^6(4(x-y)+1)</cmath>Dividing both sides, we have <cmath>(\frac{x+y}{x-y})^6=4x-4y+1</cmath> | + | Factoring, we have <cmath>(x+y)^6=(x-y)^6(4(x-y)+1)</cmath>Dividing both sides, we have <cmath>\left(\frac{x+y}{x-y}\right)^6=4x-4y+1</cmath> |
Now, since the LHS is the 6th power of a rational number, and the RHS is an integer, the RHS must be a perfect 6th power. Define <math>a=\frac{x+y}{x-y}</math>. By inspection, <math>a</math> must be a positive odd integer satistisfying <math>a \geq 3</math>. We also have <cmath>a^6=4x-4y+1</cmath> Now, we can solve for <math>x</math> and <math>y</math> in terms of <math>a</math>: | Now, since the LHS is the 6th power of a rational number, and the RHS is an integer, the RHS must be a perfect 6th power. Define <math>a=\frac{x+y}{x-y}</math>. By inspection, <math>a</math> must be a positive odd integer satistisfying <math>a \geq 3</math>. We also have <cmath>a^6=4x-4y+1</cmath> Now, we can solve for <math>x</math> and <math>y</math> in terms of <math>a</math>: | ||
<math>x-y=\frac{a^6-1}{4}</math> and <math>x+y=a(x-y)=\frac{a(a^6-1)}{4}</math>. | <math>x-y=\frac{a^6-1}{4}</math> and <math>x+y=a(x-y)=\frac{a(a^6-1)}{4}</math>. | ||
− | Now we have: <cmath>(x,y)=(\frac{(a+1)(a^6-1)}{8},\frac{(a-1)(a^6-1)}{8})</cmath> | + | Now we have: <cmath>(x,y)=\left(\frac{(a+1)(a^6-1)}{8},\frac{(a-1)(a^6-1)}{8}\right)</cmath> |
and it is trivial to check that this parameterization works for all such <math>a</math> (to keep <math>x</math> and <math>y</math> integral), which implies part (a). | and it is trivial to check that this parameterization works for all such <math>a</math> (to keep <math>x</math> and <math>y</math> integral), which implies part (a). | ||
Line 34: | Line 56: | ||
-sunfishho | -sunfishho | ||
+ | |||
+ | ==Solution <math>(1.5, x)</math> where <math>|x|>0</math>== | ||
+ | So named because it is a mix of solutions 1 and 2 but differs in other aspects. | ||
+ | After fruitless searching, let <math>x+y=a</math>, <math>x-y=b</math>. Clearly <math>a, b > 0</math>. Then <math>x=\frac{a+b}{2}, y=\frac{a-b}{2}, x^2+y^2=\frac{a^2+b^2}{2}, x^2=\frac{a^2+2ab+b^2}{4}, y^2=\frac{a^2-2ab+b^2}{4}, xy=\frac{a^2-b^2}{4}</math>. | ||
+ | |||
+ | Change the LHS to <math>xy(3x^2+y^2)(x^2+3y^2)=(a-b)(a+b)(a^2+ab+b^2)(a^2-ab+b^2)*\frac{1}{4}=(a^3-b^3)(a^3+b^3)*\frac{1}{4}=(a^6-b^6)*\frac{1}{4}</math>. Change the RHS to <math>b^7</math>. Therefore <math>(\frac{a}{b})^6=4b+1</math>. Let <math>n=\frac{a}{b}</math>, and note that <math>n</math> is an integer. Therefore <math>a=n(\frac{n^6-1}{4}), b=\frac{n^6-1}{4}</math>. Because <math>n^6 \equiv 1 (\mod{4})</math>, <math>n</math> is odd and <math>>1</math> because <math>b>0</math>. Therefore, substituting for <math>x</math> and <math>y</math> we get: <math>x=\frac{(n^4+n^2+1)(n-1)(n+1)^2}{8}, y=\frac{(n+1)(n-1)^2(n^4+n^2+1)}{8}</math>. | ||
+ | |||
+ | ==Simplified Evan Chen's Solution== | ||
+ | |||
+ | Let <math>x = da</math>, <math>y = db</math>, such that <math>gcd(a,b) = 1</math>. It's obvious <math>x > y</math>, so <math>a > b</math> | ||
+ | |||
+ | By plugging it in to the original equation, and simplifying, we get | ||
+ | |||
+ | <cmath>d = \frac{ab(a^2 + 3b^2)(3a^2 + b^2)}{(a-b)^7}</cmath> | ||
+ | |||
+ | Since d is an integer, we got: | ||
+ | |||
+ | <cmath>(a-b)^7 \mid ab(a^2 + 3b^2)(3a^2 + b^2) \: \: \: \: \: (*)</cmath> | ||
+ | |||
+ | 1. Since <math>gcd(a,b) = 1</math>, a and b can't both be even | ||
+ | |||
+ | 2. If both a and b are odd. | ||
+ | <math>a-b</math> will be even. The left hand side (*) has at least 7 factors of 2. | ||
+ | Evaluating the (*) RHS term by term, we get: | ||
+ | <cmath>a \equiv 1 \pmod{2}</cmath> | ||
+ | <cmath>b \equiv 1 \pmod{2}</cmath> | ||
+ | <cmath>a^2 + 3b^2 \equiv 4 \pmod{8}</cmath> | ||
+ | <cmath>3a^2 + b^2 \equiv 4 \pmod{8}</cmath> | ||
+ | |||
+ | the (*) RHS has only 4 factors of 2. Contradiction. | ||
+ | |||
+ | 3. Thus, <math>a-b</math> has to be odd. We want to prove <math>a-b=1</math> | ||
+ | |||
+ | We know: | ||
+ | <cmath>a \equiv b \pmod{a-b}</cmath> | ||
+ | So | ||
+ | <cmath>ab(a^2 + 3b^2)(3a^2 + b^2) \equiv 16a^6 \pmod{a-b}</cmath> | ||
+ | We can assume if <math>a-b \neq 1</math> | ||
+ | |||
+ | Since <math>a-b</math> is odd, <math>gcd(16, a-b) = 1</math> | ||
+ | |||
+ | Since <math>gcd(a, a-b) = 1</math>, <math>gcd(a^6, a-b) = 1</math> | ||
+ | |||
+ | <cmath>ab(a^2 + 3b^2)(3a^2 + b^2) \equiv 16a^6 \neq 0 \pmod{a-b}</cmath> | ||
+ | contradiction. So, <math>a-b = 1</math>. | ||
+ | |||
+ | If <math>a-b=1</math>, obviously (*) will work, d will be an integer. | ||
+ | |||
+ | So (*) <math>\Leftrightarrow</math> <math>a-b=1</math>. The proof is complete. | ||
+ | |||
+ | -Alexlikemath | ||
+ | |||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 21:08, 4 April 2021
Contents
Problem:
Consider the equation
(a) Prove that there are infinitely many pairs of positive integers satisfying the equation.
(b) Describe all pairs of positive integers satisfying the equation.
Solution 1
We have , which can be expressed as . At this point, we
think of substitution. A substitution of form is slightly derailed by the leftover x and y terms, so
instead, seeing the xy in front, we substitute . This leaves us with , so . Expanding yields . Rearranging, we have
. To satisfy this equation in integers, must obviously be a power, and further inspection shows
that it must also be odd. Also, since it is a square and all odd squares are 1 mod 8, every odd sixth power gives a
solution. Since the problem asks for positive integers, the pair does not work. We go to the next highest odd
power, or . In this case, , so the LHS is , so . Using the original
substitution yields as the first solution. We have shown part a by showing that there are an infinite
number of positive integer solutions for , which can then be manipulated into solutions for . To solve part
b, we look back at the original method of generating solutions. Define and to be the pair representing the nth
solution. Since the nth odd number is , . It follows that . From our original substitution, .
Solution 2 (and motivation)
First, we shall prove a lemma:
LEMMA:
PROOF: Expanding and simplifying the right side, we find that which proves our lemma.
Now, we have that
Rearranging and getting rid of the denominator, we have that
Factoring, we have Dividing both sides, we have
Now, since the LHS is the 6th power of a rational number, and the RHS is an integer, the RHS must be a perfect 6th power. Define . By inspection, must be a positive odd integer satistisfying . We also have Now, we can solve for and in terms of :
and .
Now we have:
and it is trivial to check that this parameterization works for all such (to keep and integral), which implies part (a).
MOTIVATION FOR LEMMA:
I expanded the LHS, noticed the coefficients were , and immediately thought of binomial coefficients. Looking at Pascal's triangle, it was then easy to find and prove the lemma.
-sunfishho
Solution where
So named because it is a mix of solutions 1 and 2 but differs in other aspects. After fruitless searching, let , . Clearly . Then .
Change the LHS to . Change the RHS to . Therefore . Let , and note that is an integer. Therefore . Because , is odd and because . Therefore, substituting for and we get: .
Simplified Evan Chen's Solution
Let , , such that . It's obvious , so
By plugging it in to the original equation, and simplifying, we get
Since d is an integer, we got:
1. Since , a and b can't both be even
2. If both a and b are odd. will be even. The left hand side (*) has at least 7 factors of 2. Evaluating the (*) RHS term by term, we get:
the (*) RHS has only 4 factors of 2. Contradiction.
3. Thus, has to be odd. We want to prove
We know: So We can assume if
Since is odd,
Since ,
contradiction. So, .
If , obviously (*) will work, d will be an integer.
So (*) . The proof is complete.
-Alexlikemath
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2017 USAJMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |