Difference between revisions of "2017 USAJMO Problems/Problem 2"

(Solution 4)
(Solution (1.5, x) where |x|>0: more reformatting)
 
(4 intermediate revisions by 2 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>.
  
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
+
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>.
 
 
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 59: 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 <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>.
+
After fruitless searching, let <math>x+y=a</math>, <math>x-y=b</math>. Clearly <math>a,b>0</math>. Then,
 
+
<cmath>\begin{align*}
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>.
+
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==
 
==Simplified Evan Chen's Solution==
Line 109: Line 112:
  
 
==Solution 4==
 
==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>.  
 
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>.  
Line 119: Line 124:
  
 
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.
 
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,
 
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,
Line 125: Line 132:
 
<cmath> = \frac{p^2}{q^7}(16p^5 + 48p^4q + 60p^3q^2 + 40p^2q^3 + 15pq^4 + 3q^5).</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>.  
+
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  
 
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  
Line 144: Line 151:
 
<cmath> = \frac{p^2}{2^3}(p^5 + 6p^4 + 15p^3 + 20p^2 + 15p + 6).</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>
+
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
 
~mathboy100

Latest revision as of 18:08, 24 April 2023

Problem

Consider the equation \[\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right) = (x-y)^7.\]

(a) Prove that there are infinitely many pairs $(x,y)$ of positive integers satisfying the equation.

(b) Describe all pairs $(x,y)$ of positive integers satisfying the equation.

Solution 1

We have $(3x^3+xy^2)(yx^2+3y^3)=(x-y)^7$, which can be expressed as $xy(3x^2+y^2)(x^2+3y^2)=(x-y)^7$. At this point, we think of substitution. A substitution of form $a=x+y, b=x-y$ is slightly derailed by the leftover x and y terms, so instead, seeing the $xy$ in front, we substitute $x=a+b, y=a-b$. This leaves us with: \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*} Rearranging, we have $b^6(8b+1)=a^6$. To satisfy this equation in integers, $8b+1$ must obviously be a $6$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 $(a,b)=(0,0)$ does not work. We go to the next highest odd $6$th power, $3^6$ or $729$. In this case, $b=91$, so the LHS is $91^6\cdot3^6=273^6$, so $a=273$. Using the original substitution yields $(x,y)=(364,182)$ as the first solution. We have shown part a by showing that there are an infinite number of positive integer solutions for $(a,b)$, which can then be manipulated into solutions for $(x,y)$.

To solve part (b), we look back at the original method of generating solutions. Define $a_n$ and $b_n$ to be the pair representing the $n$th solution. Since the $n$th odd number is $2n+1$, $b_n=\frac{(2n+1)^6-1}{8}$. It follows that $a_n=(2n+1)b_n=\frac{(2n+1)^7-(2n+1)}{8}$. From our original substitution, $(x,y)=\left(\frac{(2n+1)^7+(2n+1)^6-2n-2}{8},\frac{(2n+1)^7-(2n+1)^6-2n}{8}\right)$.

Solution 2 (and motivation)

First, we shall prove a lemma:

LEMMA:

\[\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right) = \frac{(x+y)^6-(x-y)^6}{4}\] PROOF: Expanding and simplifying the right side, we find that \[\frac{(x+y)^6-(x-y)^6}{4}=\frac{12x^5y+40x^3y^3+12xy^5}{4}\]\[=3x^5y+10x^3y^3+3xy^5\]\[=\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right)\] which proves our lemma.


Now, we have that \[\frac{(x+y)^6-(x-y)^6}{4}=(x-y)^7\] Rearranging and getting rid of the denominator, we have that \[(x+y)^6=4(x-y)^7+(x-y)^6\] Factoring, we have \[(x+y)^6=(x-y)^6(4(x-y)+1)\]Dividing both sides, we have \[\left(\frac{x+y}{x-y}\right)^6=4x-4y+1\] 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 $a=\frac{x+y}{x-y}$. By inspection, $a$ must be a positive odd integer satistisfying $a \geq 3$. We also have \[a^6=4x-4y+1\] Now, we can solve for $x$ and $y$ in terms of $a$: $x-y=\frac{a^6-1}{4}$ and $x+y=a(x-y)=\frac{a(a^6-1)}{4}$. Now we have: \[(x,y)=\left(\frac{(a+1)(a^6-1)}{8},\frac{(a-1)(a^6-1)}{8}\right)\] and it is trivial to check that this parameterization works for all such $a$ (to keep $x$ and $y$ integral), which implies part (a).


MOTIVATION FOR LEMMA: I expanded the LHS, noticed the coefficients were $(3,10,3)$, and immediately thought of binomial coefficients. Looking at Pascal's triangle, it was then easy to find and prove the lemma.

-sunfishho

Solution $(1.5, x)$ where $|x|>0$

So named because it is a mix of solutions 1 and 2 but differs in other aspects. After fruitless searching, let $x+y=a$, $x-y=b$. Clearly $a,b>0$. Then, \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*} Change the LHS of the original equation to \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*} and change the RHS to $b^7$. Therefore $\biggl(\dfrac{a}{b}\biggr)^6=4b+1$. Let $n=\frac{a}{b}$, and note that $n$ is an integer. Therefore $b=\frac{n^6-1}{4},a=bn=n\biggl(\dfrac{n^6-1}{4}\biggr)$. Because $n^6\equiv1\pmod{4}$, $n$ is odd, and thus is greater than $1$, since $b>0$. Therefore, substituting for $x$ and $y$, we get: \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*}

Simplified Evan Chen's Solution

Let $x = da$, $y = db$, such that $gcd(a,b) = 1$. It's obvious $x > y$, so $a > b$

By plugging it in to the original equation, and simplifying, we get

\[d = \frac{ab(a^2 + 3b^2)(3a^2 + b^2)}{(a-b)^7}\]

Since d is an integer, we got:

\[(a-b)^7 \mid ab(a^2 + 3b^2)(3a^2 + b^2) \: \: \: \: \: (*)\]

1. Since $gcd(a,b) = 1$, a and b can't both be even

2. If both a and b are odd. $a-b$ will be even. The left hand side (*) has at least 7 factors of 2. Evaluating the (*) RHS term by term, we get: \[a \equiv 1 \pmod{2}\] \[b \equiv 1 \pmod{2}\] \[a^2 + 3b^2 \equiv 4 \pmod{8}\] \[3a^2 + b^2 \equiv 4 \pmod{8}\]

the (*) RHS has only 4 factors of 2. Contradiction.

3. Thus, $a-b$ has to be odd. We want to prove $a-b=1$

We know: \[a \equiv b \pmod{a-b}\] So \[ab(a^2 + 3b^2)(3a^2 + b^2) \equiv  16a^6 \pmod{a-b}\] We can assume if $a-b \neq 1$

Since $a-b$ is odd, $gcd(16, a-b) = 1$

Since $gcd(a, a-b) = 1$, $gcd(a^6, a-b) = 1$

\[ab(a^2 + 3b^2)(3a^2 + b^2) \equiv  16a^6 \neq 0 \pmod{a-b}\] contradiction. So, $a-b = 1$.

If $a-b=1$, obviously (*) will work, d will be an integer.

So (*) $\Leftrightarrow$ $a-b=1$. The proof is complete.

-Alexlikemath

Solution 4

Part a:

Let $a = 1 + \frac{1}{n}$, where $n$ is a positive integer. We will show that there is precisely one solution $(x, y)$ to the equation such that $x = ay$.

If $x = ay$, we have

\[(3a^3y^3 + ay^3)(a^2y^3 + 3y^3) = ((a-1)y)^7\] \[y^6(3a^5 + 10a^3 + a) = (a-1)^7y^7\] \[\frac{3a^5 + 10a^3 + a}{(a-1)^7} = y.\]

The numerator is a multiple of $\frac{1}{n^5}$, so $y$ is an integer multiple of $n^2$. Thus, $x = \frac{n+1}{n}\cdot y$ is also an integer, and we conclude that this pair $(x, y)$ satisfies the system of equations. Because this works for any positive integer $n$, 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 $x$ and $y$. As before, set $a = 1 + \frac{1}{n}$, but this time $n = \frac{p}{q}$ in simplest terms. Then,

\[y = n^2(3(n+1)^5 + 10n^2(n+1)^3 + 3n^4(n+1))\] \[= \frac{p^2}{q^7}(16p^5 + 48p^4q + 60p^3q^2 + 40p^2q^3 + 15pq^4 + 3q^5).\]

For this to be rational, $q$ must divide the expression in brackets and thus must divide $16p^5$. However, $p$ and $q$ are relatively prime, so $q$ must divide $16$, and $p$ is therefore odd.

Next, set $q = 2^k$, where $k$ is a positive integer between $1$ and $4$, inclusive. We have

\[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).\]

The sum in the brackets must be divisible by $2^{7k}$, which is a power of $2$ greater than or equal to $2^7$. Let $z$ be this sum. Then,

\[z \equiv 16 + 0 + v + 0 + w + 0 = 16 + v + w \pmod{32},\]

where $v$ represents $15\cdot 2^{2+2k}p^3$ and $w$ represents $15\cdot 2^{4k}p$. Therefore, we must have

\[15(2^{2+k}p^3 + 2^{4k}p) \equiv 16 \pmod{32}.\]

For $k > 1$, this is equal to $0 \pmod{32}$, so we conclude that $k = 1$ (and thus $q = 2$). Then,

\[y = \frac{p^2}{2^7}(16p^5 + 96p^4 + 240p^3 + 320p^2 + 240p + 96)\] \[= \frac{p^2}{2^3}(p^5 + 6p^4 + 15p^3 + 20p^2 + 15p + 6).\]

For this to be integral, the expression in brackets must be a multiple of $8$. However, there are three terms that are odd in this expression, $p^5$, $15p^3$, and $15p$. Thus, we have a contradiction, and we conclude that the only solutions $(x, y)$ are of the form stated above. $\square$

~mathboy100

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2017 USAJMO (ProblemsResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5 6
All USAJMO Problems and Solutions