Difference between revisions of "2017 USAJMO Problems/Problem 2"
(→Solution 1) |
(→Solution (1.5, x) where |x|>0: more reformatting) |
||
(16 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
Consider the equation | Consider the equation | ||
<cmath>\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right) = (x-y)^7.</cmath> | <cmath>\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right) = (x-y)^7.</cmath> | ||
Line 8: | Line 8: | ||
==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 | + | 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 <math>xy</math> in front, we substitute <math>x=a+b, y=a-b</math>. This leaves us with: |
+ | <cmath>\begin{align*} | ||
+ | (a^2-b^2)(4a^2+4ab+4b^2)(4a^2-4ab+4b^2)&=128b^7\\ | ||
+ | (a^2-b^2)(a^2+ab+b^2)(a^2-ab+b^2)&=8b^7\\ | ||
+ | a^6-b^6&=8b^7\\ | ||
+ | \end{align*}</cmath> | ||
+ | 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>6</math><sup>th</sup> 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>6</math><sup>th</sup> 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 <math>n</math><sup>th</sup> solution. Since the <math>n</math><sup>th</sup> 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>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | <math> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | (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 62: | Line 44: | ||
==Solution <math>(1.5, x)</math> where <math>|x|>0</math>== | ==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. | 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 < | + | After fruitless searching, let <math>x+y=a</math>, <math>x-y=b</math>. Clearly <math>a,b>0</math>. Then, |
+ | <cmath>\begin{align*} | ||
+ | x&=\frac{a+b}{2}\\ | ||
+ | y&=\frac{a-b}{2}\\ | ||
+ | xy&=\frac{a^2-b^2}{4}\\ | ||
+ | x^2&=\frac{a^2+2ab+b^2}{4}\\ | ||
+ | y^2&=\frac{a^2-2ab+b^2}{4}\\ | ||
+ | x^2+y^2&=\frac{a^2+b^2}{2} | ||
+ | \end{align*}</cmath> | ||
+ | Change the LHS of the original equation to | ||
+ | <cmath>\begin{align*} | ||
+ | &\mathrel{\phantom{=}}xy(3x^2+y^2)(x^2+3y^2)\\ | ||
+ | &=(a-b)(a+b)(a^2+ab+b^2)(a^2-ab+b^2)\cdot\frac{1}{4}\\ | ||
+ | &=(a^3-b^3)(a^3+b^3)\cdot\frac{1}{4}\\ | ||
+ | &=(a^6-b^6)\cdot\frac{1}{4}, | ||
+ | \end{align*}</cmath> | ||
+ | and change the RHS to <math>b^7</math>. Therefore <math>\biggl(\dfrac{a}{b}\biggr)^6=4b+1</math>. Let <math>n=\frac{a}{b}</math>, and note that <math>n</math> is an integer. Therefore <math>b=\frac{n^6-1}{4},a=bn=n\biggl(\dfrac{n^6-1}{4}\biggr)</math>. Because <math>n^6\equiv1\pmod{4}</math>, <math>n</math> is odd, and thus is greater than <math>1</math>, since <math>b>0</math>. Therefore, substituting for <math>x</math> and <math>y</math>, we get: | ||
+ | <cmath>\begin{align*} | ||
+ | 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} | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | ==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 | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | Part a: | ||
+ | |||
+ | Let <math>a = 1 + \frac{1}{n}</math>, where <math>n</math> is a positive integer. We will show that there is precisely one solution <math>(x, y)</math> to the equation such that <math>x = ay</math>. | ||
+ | |||
+ | If <math>x = ay</math>, we have | ||
+ | |||
+ | <cmath>(3a^3y^3 + ay^3)(a^2y^3 + 3y^3) = ((a-1)y)^7</cmath> | ||
+ | <cmath>y^6(3a^5 + 10a^3 + a) = (a-1)^7y^7</cmath> | ||
+ | <cmath>\frac{3a^5 + 10a^3 + a}{(a-1)^7} = y.</cmath> | ||
+ | |||
+ | The numerator is a multiple of <math>\frac{1}{n^5}</math>, so <math>y</math> is an integer multiple of <math>n^2</math>. Thus, <math>x = \frac{n+1}{n}\cdot y</math> is also an integer, and we conclude that this pair <math>(x, y)</math> satisfies the system of equations. Because this works for any positive integer <math>n</math>, we conclude that there are infinitely many solutions to the equation. | ||
+ | |||
+ | Part b: | ||
+ | |||
+ | We will now prove that these are the only possible solutions. Suppose the contrary, that there are solutions with a different ratio between <math>x</math> and <math>y</math>. As before, set <math>a = 1 + \frac{1}{n}</math>, but this time <math>n = \frac{p}{q}</math> in simplest terms. Then, | ||
+ | |||
+ | <cmath>y = n^2(3(n+1)^5 + 10n^2(n+1)^3 + 3n^4(n+1))</cmath> | ||
+ | <cmath> = \frac{p^2}{q^7}(16p^5 + 48p^4q + 60p^3q^2 + 40p^2q^3 + 15pq^4 + 3q^5).</cmath> | ||
+ | |||
+ | For this to be rational, <math>q</math> must divide the expression in brackets and thus must divide <math>16p^5</math>. However, <math>p</math> and <math>q</math> are relatively prime, so <math>q</math> must divide <math>16</math>, and <math>p</math> is therefore odd. | ||
+ | |||
+ | Next, set <math>q = 2^k</math>, where <math>k</math> is a positive integer between <math>1</math> and <math>4</math>, inclusive. We have | ||
+ | |||
+ | <cmath>y = \frac{p^2}{2^{7k}}(2^4p^5 + 3\cdot 2^{4+k}p^4 + 15\cdot 2^{2+2k}p^3 + 5 \cdot 2^{3+3k}p^2 + 15 \cdot 2^{4k}p + 3 \cdot 2^5k).</cmath> | ||
+ | |||
+ | The sum in the brackets must be divisible by <math>2^{7k}</math>, which is a power of <math>2</math> greater than or equal to <math>2^7</math>. Let <math>z</math> be this sum. Then, | ||
+ | |||
+ | <cmath>z \equiv 16 + 0 + v + 0 + w + 0 = 16 + v + w \pmod{32}, </cmath> | ||
+ | |||
+ | where <math>v</math> represents <math>15\cdot 2^{2+2k}p^3</math> and <math>w</math> represents <math>15\cdot 2^{4k}p</math>. Therefore, we must have | ||
+ | |||
+ | <cmath>15(2^{2+k}p^3 + 2^{4k}p) \equiv 16 \pmod{32}.</cmath> | ||
+ | |||
+ | For <math>k > 1</math>, this is equal to <math>0 \pmod{32}</math>, so we conclude that <math>k = 1</math> (and thus <math>q = 2</math>). Then, | ||
+ | |||
+ | <cmath>y = \frac{p^2}{2^7}(16p^5 + 96p^4 + 240p^3 + 320p^2 + 240p + 96)</cmath> | ||
+ | <cmath> = \frac{p^2}{2^3}(p^5 + 6p^4 + 15p^3 + 20p^2 + 15p + 6).</cmath> | ||
+ | |||
+ | For this to be integral, the expression in brackets must be a multiple of <math>8</math>. However, there are three terms that are odd in this expression, <math>p^5</math>, <math>15p^3</math>, and <math>15p</math>. Thus, we have a contradiction, and we conclude that the only solutions <math>(x, y)</math> are of the form stated above. <math>\square</math> | ||
− | + | ~mathboy100 | |
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 19:08, 24 April 2023
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
in front, we substitute
. This leaves us with:
Rearranging, we have
. To satisfy this equation in integers,
must obviously be a
th 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
th 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
th solution. Since the
th 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 ![$|x|>0$](//latex.artofproblemsolving.com/1/4/c/14c055d37aa27d18b8a4579ecd83f7b876a1f847.png)
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 of the original equation to
and change the RHS to
. Therefore
. Let
, and note that
is an integer. Therefore
. Because
,
is odd, and thus is greater than
, since
. 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
Solution 4
Part a:
Let , where
is a positive integer. We will show that there is precisely one solution
to the equation such that
.
If , we have
The numerator is a multiple of , so
is an integer multiple of
. Thus,
is also an integer, and we conclude that this pair
satisfies the system of equations. Because this works for any positive integer
, we conclude that there are infinitely many solutions to the equation.
Part b:
We will now prove that these are the only possible solutions. Suppose the contrary, that there are solutions with a different ratio between and
. As before, set
, but this time
in simplest terms. Then,
For this to be rational, must divide the expression in brackets and thus must divide
. However,
and
are relatively prime, so
must divide
, and
is therefore odd.
Next, set , where
is a positive integer between
and
, inclusive. We have
The sum in the brackets must be divisible by , which is a power of
greater than or equal to
. Let
be this sum. Then,
where represents
and
represents
. Therefore, we must have
For , this is equal to
, so we conclude that
(and thus
). Then,
For this to be integral, the expression in brackets must be a multiple of . However, there are three terms that are odd in this expression,
,
, and
. Thus, we have a contradiction, and we conclude that the only solutions
are of the form stated above.
~mathboy100
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 |