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 USAJMO Problems/Problem 1"

m (→‎Solution 2)
Line 11: Line 11:
 
Sidenote: Actually, for <math>N=3</math>, the members are all reduced to the average, as the sum of the terms is constant and does not change.
 
Sidenote: Actually, for <math>N=3</math>, the members are all reduced to the average, as the sum of the terms is constant and does not change.
  
−
==Solution 2==
+
==Solution 2 (INCORRECT)==
 
Let the set be <math>{a_1,a_2,\dots ,a_{2015}}</math>, where all the terms are nonnegative. Note that the sum of all the terms in this sequence will always be the same after any amount of moves. To prove this, let <math>i,j</math> be integers with <math>1\le i<j\le 2015</math>, and we have <math>a_i+a_j = \frac{a_i+a_j}{2}+\frac{a_i+a_j}{2}</math>.
 
Let the set be <math>{a_1,a_2,\dots ,a_{2015}}</math>, where all the terms are nonnegative. Note that the sum of all the terms in this sequence will always be the same after any amount of moves. To prove this, let <math>i,j</math> be integers with <math>1\le i<j\le 2015</math>, and we have <math>a_i+a_j = \frac{a_i+a_j}{2}+\frac{a_i+a_j}{2}</math>.
  
Line 18: Line 18:
 
Finally, note that <math>a_1a_2\dots a_{2015}\le (\frac{a_1+a_2+\dots +a_{2015}}{2015})^{2015}</math> by AM-GM, so because <math>a_1+a_2+\dots +a_{2015}</math> is fixed, there is a maximum product that is reached after a finite number of moves as the product increases. This product is reached when <math>a_1=a_2=\dots =a_{2015}</math>, so we are done.
 
Finally, note that <math>a_1a_2\dots a_{2015}\le (\frac{a_1+a_2+\dots +a_{2015}}{2015})^{2015}</math> by AM-GM, so because <math>a_1+a_2+\dots +a_{2015}</math> is fixed, there is a maximum product that is reached after a finite number of moves as the product increases. This product is reached when <math>a_1=a_2=\dots =a_{2015}</math>, so we are done.
  
−
 
+
This solution is incorrect; the product may take an infinite number of moves to reach the maximum (for example, consider the sequence <math>1, 3, 4, 5... 2016</math>)
  
  

Revision as of 13:32, 28 June 2019

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.

Solution

Let the set be ${-1007, -1006, ...0,1,2...1006, 1007}$, namely all the consecutive integers from $-1007$ to $1007$. Notice that the operation we are applying in this problem does not change the sum or the mean of the set, which is $0$.

There are $1007$ pairs of opposite integers $\{a,-a\}$. After the first two elements are chosen, there are at least $1005$ such pairs. 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: ${a_1,a_2,a_3,a_4,a_5,a_6=0,a_7=0,a_8=0}$, and perform the operation in the following order: \[(a_1,a_2)\to(m_1,m_1), (a_3,a_4)\to(m_2,m_2), (a_5,a_6)\to(m_3,m_3), (a_7,a_8)\to(m_4,m_4),\] where $m_i=\frac{a_i+a_{i+1}}{2}$. Then, $(m_1,m_2)\to(m_{11}, m_{11})$ for two groups, $(m_3,m_4)\to(m_{12}, m_{12})$ for the other two groups, and finally $(m_{11},m_{12})\to(m_{111}, m_{111})$ for all the eight elements. Since the sum of the eight-group is $0$, $m_{111}$ must also be $0$. Therefore, all the elements are reduced to $0$.

The key to the algorithm is to form a $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\ge 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\ge4$ 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.

Sidenote: Actually, for $N=3$, the members are all reduced to the average, as the sum of the terms is constant and does not change.

Solution 2 (INCORRECT)

Let the set be ${a_1,a_2,\dots ,a_{2015}}$, where all the terms are nonnegative. Note that the sum of all the terms in this sequence will always be the same after any amount of moves. To prove this, let $i,j$ be integers with $1\le i<j\le 2015$, and we have $a_i+a_j = \frac{a_i+a_j}{2}+\frac{a_i+a_j}{2}$.

Also, $a_ia_j \le (\frac{a_i+a_j}{2})(\frac{a_i+a_j}{2})$ by AM-GM, so the product of all the terms will not decrease after any number of moves. However, the product will only stay the same when $a_i=a_j$, so the product will always increase if $a_i\ne a_j$.

Finally, note that $a_1a_2\dots a_{2015}\le (\frac{a_1+a_2+\dots +a_{2015}}{2015})^{2015}$ by AM-GM, so because $a_1+a_2+\dots +a_{2015}$ is fixed, there is a maximum product that is reached after a finite number of moves as the product increases. This product is reached when $a_1=a_2=\dots =a_{2015}$, so we are done.

This solution is incorrect; the product may take an infinite number of moves to reach the maximum (for example, consider the sequence $1, 3, 4, 5... 2016$)


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

See also

2015 USAJMO (Problems • Resources)
First Problem Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_USAJMO_Problems/Problem_1&oldid=107059"