Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2015 USAMO Problems/Problem 1"

m (Added problem)
m (added my solution)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
===Problem===
 
===Problem===
−
Given a sequence of real numbers, a move consists of choosing two terms and replacing each with their arithmetic mean. Show that there exists a sequence of 2015 distinct real numbers such that after one initial move is applied to the sequence -- no matter what move -- there is always a way to continue with a finite sequence of moves so as to obtain in the end a constant sequence.
+
Solve in integers the equation
 +
<cmath> x^2+xy+y^2 = \left(\frac{x+y}{3}+1\right)^3. </cmath>
 +
===Solution===
 +
We first notice that both sides must be integers, so <math>\frac{x+y}{3}</math> must be an integer.  
 +
 
 +
We can therefore perform the substitution <math>x+y = 3t</math> where <math>t</math> is an integer.  
 +
 
 +
Then:
  
−
===Solution===
+
<math>(3t)^2 - xy = (t+1)^3</math>
−
Let the set be {-1007, -1006, ...0,1,2...1006, 1007}, namely all the consecutive integers from -1007 to 1007.  Notice that the operation does not change the sum or the mean of the set, which is 0. 
+
 
 +
<math>9t^2 + x (x - 3t) = t^3 + 3t^2 + 3t + 1</math>
 +
 
 +
<math>4x^2 - 12xt + 9t^2 = 4t^3 - 15t^2 + 12t + 4</math>
 +
 
 +
<math>(2x - 3t)^2 = (t - 2)^2(4t + 1)</math>
 +
 
 +
<math>4t+1</math> is therefore the square of an odd integer and can be replaced with <math>(2n+1)^2 = 4n^2 + 4n +1</math>
 +
 
 +
By substituting using <math>t = n^2 + n</math> we get:
 +
 
 +
<math>(2x - 3n^2 - 3n)^2 = [(n^2 + n - 2)(2n+1)]^2</math>
 +
 
 +
<math>2x - 3n^2 - 3n = \pm (2n^3 + 3n^2 -3n -2)</math>
 +
 
 +
<math>x = n^3 + 3n^2 - 1</math> or <math>x = -n^3 + 3n + 1</math>
 +
 
 +
Using substitution we get the solutions: <math>(n^3 + 3n^2 - 1, -n^3 + 3n + 1) \cup (-n^3 + 3n + 1, n^3 + 3n^2 - 1)</math>
  
−
There are 1007 pairs of opposite integers {a,-a}. After the first two elements are chosen, there are at least 1005 such pair. For each such pair we perform the operation of average, hence reducing these 2010 elements to 0. Then use the other 5 elements together with three 0's produced to form the group of eight: {a1,a2,a3,a4,a5,a6=0,a7=0,a8=0}, and perform the operation in the following order: (a1,a2)-> (m1,m1), (a3,a4)->(m2,m2),       (a3,a4)->(m3,m3), (a3,a4)->(m4,m4), where m1=(a1+a2)/2, etc. Then, (m1,m2)->(m11, m11) for two groups, (m3,m4)->(m12,m12) for the other two groups, and finally (m11,m12) -> (m111, m111) for all the eight elements. Since the sum of the eight-group is 0, m111 must also be 0. Therefore, all the elements are reduced to 0.
+
==Solution 2==
 +
Let <math>n = \frac{x+y}{3}</math>.
 +
Thus, <math>x+y = 3n</math>.
 +
We have
 +
<cmath>x^2+xy+y^2 = \left(\frac{x+y}{3}+1\right)^3 \implies (x+y)^2 - xy = \left(\frac{x+y}{3}+1\right)^3</cmath>
 +
Substituting <math>n</math> for <math>\frac{x+y}{3}</math>, we have
 +
<cmath>9n^2 - x(3n-x) = (n+1)^3</cmath>
 +
Treating <math>x</math> as a variable and <math>n</math> as a constant, we have
 +
<cmath>9n^2 - 3nx + x^2 = (n+1)^3,</cmath>
 +
which turns into
 +
<cmath>x^2 - 3nx + (9n^2 - (n+1)^3) = 0,</cmath>
 +
a quadratic equation.
 +
By the quadratic formula,  
 +
<cmath>x = \frac{1}{2} \left(3n \pm \sqrt{9n^2 - 4(9n^2 - (n+1)^3)} \right)</cmath>
 +
which simplifies to
 +
<cmath>x = \frac{1}{2} \left(3n \pm \sqrt{4(n+1)^3 - 27n^2} \right)</cmath>
 +
Since we want <math>x</math> and <math>y</math> to be integers, we need <math>4(n+1)^3 - 27n^2</math> to be a perfect square.
 +
We can factor the aforementioned equation to be <cmath>(n-2)^2 (4n+1) = k^2</cmath>
 +
for an integer <math>k</math>.
 +
Since <math>(n-2)^2</math> is always a perfect square, for <math>(n-2)^2 (4n+1)</math> to be a perfect square, <math>4n + 1</math> has to be a perfect square as well.
 +
Since <math>4n + 1</math> is odd, the square root of the aforementioned equation must be odd as well.
 +
Thus, we have <math>4n + 1 = a^2</math> for some odd <math>a</math>.
 +
Thus, <cmath>n = \frac{a^2 - 1}{4}, </cmath> in which by difference of squares it is easy to see that all the possible values for <math>n</math> are just <math>n = p(p-1)</math>, where <math>p</math> is a positive integer.
 +
Thus, <cmath>x+y = 3n = 3p(p-1).</cmath>
 +
Thus, the general form for <cmath>x = \frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right)</cmath> for a positive integer <math>p</math>.
 +
(This is an integer since <math>4(p(p-1)+1)^3 - 27(p(p-1))^2</math> is an even perfect square (since <math>4(p(p-1)+1)</math> is always even, as well as <math>27(p(p-1))^2</math> being always even) as established, and <math>3p(p-1)</math> is always even as well. Thus, the whole numerator is even, which makes the quantity of that divided by <math>2</math> always an integer.)
 +
Since <math>y = 3n - x</math>, the general form for <math>y</math> is just
 +
<cmath>y = 3p(p-1) - \frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right)</cmath>
 +
(This is an integer since <math>4(p(p-1)+1)^3 - 27(p(p-1))^2</math> is an even perfect square (since <math>4(p(p-1)+1)</math> is always even, as well as <math>27(p(p-1))^2</math> being always even) as established, and <math>3p(p-1)</math> is always even as well. Thus, the whole numerator is even, which makes the quantity of that divided by <math>2</math> always an integer, which thus trivially makes <cmath>3p(p-1) - \frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right)</cmath> an integer.)
 +
for a positive integer <math>p</math>.
 +
Thus, our general in integers <math>(x, y)</math> is <cmath>(\frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right), 3p(p-1) - \frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right).</cmath>
 +
<math>\boxed{}</math>
  
−
The key to the algorithm is to form 2^k subset, which is guaranteed to be reducible to all the members of the same value, namely the mean. Then before that if we could always choose M >=N-2^k members to form pairs, each yielding the average of the total group, then all the members are reduced to the average. Under the condition that two arbitrary elements are chosen first, we need only N>=4 to guarantee this result. But for N=2 the first operation leads to equal elements, so N=3 is the only case when all the members may not be reduced to average.
+
-fidgetboss_4000

Latest revision as of 21:42, 15 March 2020

Problem

Solve in integers the equation \[x^2+xy+y^2 = \left(\frac{x+y}{3}+1\right)^3.\]

Solution

We first notice that both sides must be integers, so $\frac{x+y}{3}$ must be an integer.

We can therefore perform the substitution $x+y = 3t$ where $t$ is an integer.

Then:

$(3t)^2 - xy = (t+1)^3$

$9t^2 + x (x - 3t) = t^3 + 3t^2 + 3t + 1$

$4x^2 - 12xt + 9t^2 = 4t^3 - 15t^2 + 12t + 4$

$(2x - 3t)^2 = (t - 2)^2(4t + 1)$

$4t+1$ is therefore the square of an odd integer and can be replaced with $(2n+1)^2 = 4n^2 + 4n +1$

By substituting using $t = n^2 + n$ we get:

$(2x - 3n^2 - 3n)^2 = [(n^2 + n - 2)(2n+1)]^2$

$2x - 3n^2 - 3n = \pm (2n^3 + 3n^2 -3n -2)$

$x = n^3 + 3n^2 - 1$ or $x = -n^3 + 3n + 1$

Using substitution we get the solutions: $(n^3 + 3n^2 - 1, -n^3 + 3n + 1) \cup (-n^3 + 3n + 1, n^3 + 3n^2 - 1)$

Solution 2

Let $n = \frac{x+y}{3}$. Thus, $x+y = 3n$. We have \[x^2+xy+y^2 = \left(\frac{x+y}{3}+1\right)^3 \implies (x+y)^2 - xy = \left(\frac{x+y}{3}+1\right)^3\] Substituting $n$ for $\frac{x+y}{3}$, we have \[9n^2 - x(3n-x) = (n+1)^3\] Treating $x$ as a variable and $n$ as a constant, we have \[9n^2 - 3nx + x^2 = (n+1)^3,\] which turns into \[x^2 - 3nx + (9n^2 - (n+1)^3) = 0,\] a quadratic equation. By the quadratic formula, \[x = \frac{1}{2} \left(3n \pm \sqrt{9n^2 - 4(9n^2 - (n+1)^3)} \right)\] which simplifies to \[x = \frac{1}{2} \left(3n \pm \sqrt{4(n+1)^3 - 27n^2} \right)\] Since we want $x$ and $y$ to be integers, we need $4(n+1)^3 - 27n^2$ to be a perfect square. We can factor the aforementioned equation to be \[(n-2)^2 (4n+1) = k^2\] for an integer $k$. Since $(n-2)^2$ is always a perfect square, for $(n-2)^2 (4n+1)$ to be a perfect square, $4n + 1$ has to be a perfect square as well. Since $4n + 1$ is odd, the square root of the aforementioned equation must be odd as well. Thus, we have $4n + 1 = a^2$ for some odd $a$. Thus, \[n = \frac{a^2 - 1}{4},\] in which by difference of squares it is easy to see that all the possible values for $n$ are just $n = p(p-1)$, where $p$ is a positive integer. Thus, \[x+y = 3n = 3p(p-1).\] Thus, the general form for \[x = \frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right)\] for a positive integer $p$. (This is an integer since $4(p(p-1)+1)^3 - 27(p(p-1))^2$ is an even perfect square (since $4(p(p-1)+1)$ is always even, as well as $27(p(p-1))^2$ being always even) as established, and $3p(p-1)$ is always even as well. Thus, the whole numerator is even, which makes the quantity of that divided by $2$ always an integer.) Since $y = 3n - x$, the general form for $y$ is just \[y = 3p(p-1) - \frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right)\] (This is an integer since $4(p(p-1)+1)^3 - 27(p(p-1))^2$ is an even perfect square (since $4(p(p-1)+1)$ is always even, as well as $27(p(p-1))^2$ being always even) as established, and $3p(p-1)$ is always even as well. Thus, the whole numerator is even, which makes the quantity of that divided by $2$ always an integer, which thus trivially makes \[3p(p-1) - \frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right)\] an integer.) for a positive integer $p$. Thus, our general in integers $(x, y)$ is \[(\frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right), 3p(p-1) - \frac{1}{2} \left(3p(p-1) \pm \sqrt{4(p(p-1)+1)^3 - 27(p(p-1))^2} \right).\] $\boxed{}$

-fidgetboss_4000

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_1&oldid=119480"