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

Latest revision as of 19:13, 26 July 2022

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

Consider any arithmetic sequence. WLOG, let it be $s = (1, 2, 3, \dots, 2015)$ , i.e. $s_i = i\ \forall\ 1\le i\le 2015$ . Define the move $(x, y)$ as replacing the numbers located at positions $x$ and $y$ with their mean, assuming $x$ and $y$ are distinct. If they are the same integer, define it as not making a move. Now, suppose the initial move $m_0 = (a, b)$ . If $a+b=2016$ , then $s_a = s_b = \frac{a+b}{2} = 1008$ . Then, applying the moves $m_1 = (1, 2015), m_2 = (2, 2014), \dots, m_{1007} = (1007, 1009),$ we get $s_1 = s_2 = \cdots = s_{2015} = 1008$ . Otherwise, suppose $a+b\ne 2016$ . Then consider the following $3$ moves: $m_{-1} = (2016-a, 2016-b), m_{-2} = (a, 2016-a), m_{-3} = (b, 2016-b)$ We have $m_{-1}$ makes $s_{2016-a} = s_{2016-b} = 2016 - \frac{a+b}{2}$ . So, $m_{-2}$ makes $s_a = s_{2016-a} = \frac{2016 - \frac{a+b}{2} + \frac{a+b}{2}}{2} = 1008$ Similarly for $m_{-3}$ with $s_b$ and $s_{2016-b}$ . Then, finishing up with the moves $m_1 = (1, 2015), m_2 = (2, 2014), \dots, m_{1007} = (1007, 1009),$ we get $s_1 = s_2 = \cdots = s_{2015} = 1008$ .

(95% Sure) Doesn't this solution fail for Case $2$ when $a$ or $b$ is $1008$ ? (Because $2016-1008 = 1008$ so $m_{-1}$ is basically non-existent.) - ike.chen

Solution 3 (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$ )

Solution 4

We claim that the sequence $-1007, -1006, ... ,0, ... , 1006, 1007$ satisifes the conditions

Let the initial pair that we choose to operate on be denoted as $(a, b)$

Case 1: $(a, b)$ $\neq$ $0$

Sub case 1a: if $a + b$ sum to $0$ in this sequence, the pair is really just $(a, -a)$ or $(-a, a)$ . If we replace $a$ , and $-a$ with their AM then they both become $0$ . Notice that for every number in the original sequence, there is either a negative or positive value to that (depending on the sign). So once we convert the initial pair to $0$ , we can do so for every other pair, for example let $a_i$ be a number in the sequence, we would operate on $(a_i, -a_i)$ for every number until every number in the sequence becomes $0$ . (Note that the amount of operations this would take is finite).

Sub case 1b: If $a + b \neq 0$ then we can use the same logic, but with one extra step. After we do $(a, b)$ as our initial operation, we do $(-a, -b)$ . This is equivalent to $(-a, a)$ and $(-b, b)$ which turns all those values into $0$ (this is also the same as comparing $(a+b)/2$ and $(-a-b)/2$ which cancels out). Then since the only values that remain besides $0$ both have a negative/positive counter part, do the same thing in Sub case 1a; $(a_i, -a_i)$ turning the whole sequence to $0$ in a finite number of operations.

Case 2: The inital pair is $(0, b)$

Obviously, there is a $-b$ in the sequence, (this will come into play later). Since $b \neq 0$ our only $0$ vanishes due to the AM, our goal is to make another $0$ . Remember that for every number in the original sequence (besides $0$ ) there is a negative or positive value depending on the numbers sign. So even if $b$ to $-b$ or any other number in the sequence doesn't make $0$ , we have another option.

Find any $(a, -a)$ such that $(a + -a) = 0$ (again this is guaranteed to be in the sequence).

Now once you have your $0$ s, take the $-b$ , and take the AM of that and $0$ . Then there will be 2 $-b/2$ s. This will make $0$ s with our two numbers from $(0, b)$ since that produces 2 $b/2$ s. Since those cancel and make $0$ , everything else is the same positive negative condition, which finishes. ~dukcrantel

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

@@ 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.
+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 <math>2015</math> 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===
+==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 does not change the sum or the mean of the set, which is 0.
+Let the set be <math>{-1007, -1006, ...0,1,2...1006, 1007}</math>, namely all the consecutive integers from <math>-1007</math> to <math>1007</math>.  Notice that the operation we are applying in this problem does not change the sum or the mean of the set, which is <math>0</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),       (a5,a6)->(m3,m3), (a7,a8)->(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.
+There are <math>1007</math> pairs of opposite integers <math>\{a,-a\}</math>. After the first two elements are chosen, there are at least <math>1005</math> such pairs. For each such pair we perform the operation of average, hence reducing these <math>2010</math> elements to <math>0</math>. Then use the other <math>5</math> elements together with three <math>0</math>'s produced to form the group of eight: <math>{a_1,a_2,a_3,a_4,a_5,a_6=0,a_7=0,a_8=0}</math>, and perform the operation in the following order: <cmath>(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),</cmath> where <math>m_i=\frac{a_i+a_{i+1}}{2}</math>. Then, <math>(m_1,m_2)\to(m_{11}, m_{11})</math> for two groups, <math>(m_3,m_4)\to(m_{12}, m_{12})</math> for the other two groups, and finally <math>(m_{11},m_{12})\to(m_{111}, m_{111})</math> for all the eight elements. Since the sum of the eight-group is <math>0</math>, <math>m_{111}</math> must also be <math>0</math>. Therefore, all the elements are reduced to <math>0</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.
+The key to the algorithm is to form a <math>2^k</math> 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 <math>M\ge N-2^k</math> 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 <math>N\ge4</math> to guarantee this result. But for <math>N=2</math> the first operation leads to equal elements, so <math>N=3</math> is the only case when all the members may not be reduced to average.
+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 ==
+Consider any arithmetic sequence. WLOG, let it be <math>s = (1, 2, 3, \dots, 2015)</math>, i.e. <math>s_i = i\ \forall\ 1\le i\le 2015</math>. Define the move <math>(x, y)</math> as replacing the numbers located at positions <math>x</math> and <math>y</math> with their mean, assuming <math>x</math> and <math>y</math> are distinct. If they are the same integer, define it as not making a move. Now, suppose the initial move <math>m_0 = (a, b)</math>. If <math>a+b=2016</math>, then <math>s_a = s_b = \frac{a+b}{2} = 1008</math>. Then, applying the moves
+<cmath>m_1 = (1, 2015), m_2 = (2, 2014), \dots, m_{1007} = (1007, 1009),</cmath>
+we get <math>s_1 = s_2 = \cdots = s_{2015} = 1008</math>.
+Otherwise, suppose <math>a+b\ne 2016</math>. Then consider the following <math>3</math> moves:
+<cmath>m_{-1} = (2016-a, 2016-b), m_{-2} = (a, 2016-a), m_{-3} = (b, 2016-b)</cmath>
+We have <math>m_{-1}</math> makes <math>s_{2016-a} = s_{2016-b} = 2016 - \frac{a+b}{2}</math>. So, <math>m_{-2}</math> makes
+<cmath>s_a = s_{2016-a} = \frac{2016 - \frac{a+b}{2} + \frac{a+b}{2}}{2} = 1008</cmath>
+Similarly for <math>m_{-3}</math> with <math>s_b</math> and <math>s_{2016-b}</math>. Then, finishing up with the moves
+<cmath>m_1 = (1, 2015), m_2 = (2, 2014), \dots, m_{1007} = (1007, 1009),</cmath>
+we get <math>s_1 = s_2 = \cdots = s_{2015} = 1008</math>.
+(95% Sure) Doesn't this solution fail for Case <math>2</math> when <math>a</math> or <math>b</math> is <math>1008</math>? (Because <math>2016-1008 = 1008</math> so <math>m_{-1}</math> is basically non-existent.)
+- ike.chen
+==Solution 3 (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>.
+Also, <math>a_ia_j \le (\frac{a_i+a_j}{2})(\frac{a_i+a_j}{2})</math> 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 <math>a_i=a_j</math>, so the product will always increase if <math>a_i\ne a_j</math>.
+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>)
+==Solution 4==
+We claim that the sequence <math>-1007, -1006, ... ,0, ... , 1006, 1007</math> satisifes the conditions
+Let the initial pair that we choose to operate on be denoted as <math>(a, b)</math>
+Case 1: <math>(a, b)</math> <math>\neq</math> <math>0</math>
+Sub case 1a: if <math>a + b</math> sum to <math>0</math> in this sequence, the pair is really just <math>(a, -a)</math> or <math>(-a, a)</math>. If we replace <math>a</math>, and <math>-a</math> with their AM then they both become <math>0</math>. Notice that for every number in the original sequence, there is either a negative or positive value to that (depending on the sign). So once we convert the initial pair to <math>0</math>, we can do so for every other pair, for example let <math>a_i</math> be a number in the sequence, we would operate on <math>(a_i, -a_i)</math> for every number until every number in the sequence becomes <math>0</math>. (Note that the amount of operations this would take is finite).
+Sub case 1b: If <math>a + b \neq 0</math> then we can use the same logic, but with one extra step. After we do <math>(a, b)</math> as our initial operation, we do <math>(-a, -b)</math>. This is equivalent to <math>(-a, a)</math> and <math>(-b, b)</math> which turns all those values into <math>0</math> (this is also the same as comparing <math>(a+b)/2</math> and <math>(-a-b)/2</math> which cancels out). Then since the only values that remain besides <math>0</math> both have a negative/positive counter part, do the same thing in Sub case 1a; <math>(a_i, -a_i)</math> turning the whole sequence to <math>0</math> in a finite number of operations.
+Case 2: The inital pair is <math>(0, b)</math>
+Obviously, there is a <math>-b</math> in the sequence, (this will come into play later). Since <math>b \neq 0</math> our only <math>0</math> vanishes due to the AM, our goal is to make another <math>0</math>. Remember that for every number in the original sequence (besides <math>0</math>) there is a negative or positive value depending on the numbers sign. So even if <math>b</math> to <math>-b</math> or any other number in the sequence doesn't make <math>0</math>, we have another option.
+Find any <math>(a, -a)</math> such that <math>(a + -a) = 0</math> (again this is guaranteed to be in the sequence).
+Now once you have your <math>0</math>s, take the <math>-b</math>, and take the AM of that and <math>0</math>. Then there will be 2 <math>-b/2</math>s. This will make <math>0</math>s with our two numbers from <math>(0, b)</math> since that produces 2 <math>b/2</math>s. Since those cancel and make <math>0</math>, everything else is the same positive negative condition, which finishes. ~dukcrantel
+{{MAA Notice}}
+==See also==
+{{USAJMO newbox|year=2015|beforetext=|before=First Problem|num-a=2}}

2015 USAJMO (Problems • Resources)
First Problem	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search