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.
Problem
Source: USAJMO 2015 Problem 1
Tags: AMC, USA(J)MO, USAJMO
29.04.2015 00:26
29.04.2015 00:29
But wait can't you only make a pair of 0's at a time? So if at any point, if you have no 0's aren't you screwed.
29.04.2015 00:30
That's why I mention the thing with $c$; it ensures that I have at least one $0$ in the second case. This is also what caused me the biggest headache until I realized the solution, since I had so much trouble realizing that you could create new $0$s for numbers larger than $5$.
29.04.2015 00:38
I proved that $(a_1+a_2+a_3...a_{1024})/1024=(a_{1025}...a_{1536})/512..$ etc which works.
29.04.2015 00:40
hwl0304 wrote: I proved that $(a_1+a_2+a_3...a_{1024})/1024=(a_{1025}...a_{1536})/512..$ etc which works. That's what I did.
29.04.2015 00:43
Do you guys think it will get 7?
29.04.2015 00:44
Could you elaborate on your proof?
29.04.2015 00:44
For brian's example sequence, what do you do if we make a move between 0 and some other number, x? What strategy do we use to make an odd number of zeroes? Sorry, I still can't see how this works.
29.04.2015 00:47
like let the 2 numbers chosen be a_1, a_2. move a_3 with a_4, a_5 with a_6... we get a leftover of a_2015. Then do the same for (a_1+a_2)/2 and (a_3+a_4)/2,etc. then 2015=11111011111_2 so the thing i had above: $(a_1+a_2+a_3...a_{1024})/1024=(a_{1025}...a_{1536})/512=...=(a_{2013}+a_{2014}/2)=a_{2015}$, with 1024 'copies' for (a_1+a_2+a_3...a_{1024})/1024, etc. this clearly works.
29.04.2015 00:48
Ummm... no. $a_{2015}$ won't be equal to all the rest of the terms of the sequence. EDIT: It looks like you're assuming that you have some control over the first move? You do not.
29.04.2015 00:50
why?????
29.04.2015 00:53
So here is basically what I submitted: Each move can create an even number of zeroes, so it is impossible to reach all 0's if you start with all nonzero numbers, since there are an odd number of terms. (WLOG the average of the sequence is 0).
29.04.2015 01:03
I did the same thing as brian22 except I used 1,2,3,...2015 since I thought it would make for easier writing.
29.04.2015 01:04
How many points would one get for mentioning an arithmetic sequence and the symmetry stuff, but forgetting the case where one of the points is the median?
29.04.2015 01:16
Maybe like 4-5 I think. The median case threw me off for a really long time because when I did a move with the terms -a and a, I just threw them out instead of putting 0,0.
29.04.2015 01:19
how many points would me/joey get?
29.04.2015 01:19
Wait it said "given a sequence", so doesn't it mean that you have to prove it for any sequence?
29.04.2015 01:20
No, because later the problem says "Show that there exists a sequence of 2015 distinct real numbers..."
29.04.2015 01:22
stephcurry wrote: Wait it said "given a sequence", so doesn't it mean that you have to prove it for any sequence? The first sentence is just telling you what you can do to any sequence that you already have. So, at any point, to from one sequence that you have to another, you can replace two numbers with their average. It's not asserting that every sequence will be able to be reduced to constants using this move, but rather just telling you what move is allowed.
18.11.2021 13:09
A different solution: Lemma: Given any $2^k$ ($k \ge 0$) real numbers we can make them all equal to their average. Proof: Just induct on $k$. $\square$ Now pick any $2015$ ($= 1007 + 1007 + 1$) distinct real numbers $a_1,a_2,\ldots,a_{1007},b_1,b_2,\ldots,b_{1007},c$ such that $a_i + b_i = c ~ \forall ~ i$. Now no matter what the first move is, by combining $a_i,b_i$ for many values of $i$ we can make at least $991$ of the numbers equal to $c$. Now among the leftover $1024 = 2^{10}$ numbers (which will have average $c$), we can make all them to equal $c$ because of our lemma, so done! $\blacksquare$
28.12.2021 20:41
Nice problem We claim that the sequence $\{ 1, 3, 5, \dots, 4029\}$ satisfies the given condition. Notice that the sum of all the elements of the sequence is an invariant. Thus at the end all of the elements should be equal to $2015$. We will split this numbers into pairs. \[ (1, 4030-1), (3, 4030-3), \dots, (2013, 2017), (2015) \]The last "pair" is special: it only has 1 number. Notice that all of these pairs except for the "special pair" have a sum of $4030$. Now we will do casework on which two numbers we choose. Case 1. The two numbers that we initially choose are from normal pairs i.e not from the "special pair" Notice that we don't have to care about the other pairs because we can just do an operation on each of the pairs and we will have the sequence of just 2015's. Then we have two pairs $(a, b)$ and $(c, d)$ such that $a+b=c+d=4030$. WLOG we chose $a$ and $c$. Then we have \begin{align*} \left\{ \frac{a+c}{2}, \frac{a+c}{2}, b, d \right\} &\to \left\{ \frac{a+c}{2}, \frac{a+c}{2}, \frac{b+d}{2}, \frac{b+d}{2} \right\} \\ &\to \left\{ \frac{a+b+c+d}{4}, \frac{a+b+c+d}{4} \right\} \\ &\to \left\{ 2015, 2015 \right\} \end{align*} Case 2. One of the numbers that we choose is the "special pair" We have two pairs $(a, b)$ and $(2015)$. Remember that we also have $a+b=4030$. Assume that we choose $2015$ and $a$. Then the sequence is $\left\{ \frac{2015+a}{2}, \frac{2015+a}{2}, b\right\}$. Now since the other pairs we did the operation so we have $2012$ 2015's. Now assume that we take any one of those $2015$'s and insert it into this sequence. Then we have \begin{align*} \left\{ \frac{2015+a}{2}, \frac{2015+a}{2}, b, 2015 \right\} &\to \left\{ \frac{2015+a}{2}, \frac{2015+a}{2}, \frac{2015+b}{2}, \frac{2015+b}{2} \right\} \\ &\to \left\{ \frac{4030+a+b}{4}, \frac{4030+a+b}{4} \right\} \\ &\to \left\{ 2015, 2015 \right\} \end{align*}
09.01.2022 06:03
Let the sequence be $-1007, -1006, -1005, -1004, \ldots 1004, 1005, 1006, 1007$. Call a move $(a,b)$, where we replace $a$ and $b$ with $\frac{a+b}{2}$. Also, call a pair move the move $(x,-x)$ for some $-1007\le x\le 1007$ and $x\ne0$. Case 1: The initial move $(a,b)$ satisfies $a=0$. Clearly $b\ne0$. Then we replace $0$ and $b$ with $\frac{b}{2}$. Now make the pair move for all $x$ so that $-1007\le x\le 1007, x\ne0,b,-b$. Then our sequence is $0,0,0,0,\ldots,0,0,\frac{b}{2},\frac{b}{2},-b$. Make the move $(-b,0)$. Now we make the pair move $\left(\frac{b}{2},-\frac{b}{2}\right)$ twice, so our sequence is all zeroes. Case 2: The initial move $(a,b)$ satisfies $a\ne0$ and $b=-a$. Note $a$ and $-a$ are both replaced by $0$. Then we make the pair move for all $x$ so that $-1007\le x\le 1007, x\ne0,a,-a$. So our sequence is all zeroes. Case 3: The initial move $(a,b)$ satisfies $a\ne0, b\ne0, b\ne -a$. Then we replace $a$ and $b$ with $\frac{a+b}{2}$. Now we make the move $(-a,-b)$, so both of these are replaced with $-\frac{a+b}{2}$. Then we make the pair move for all $x$ with $-1007\le x\le 1007, x\ne0, a, -a, b, -b$ as well as for $x=\frac{a+b}{2}$. Note that our sequence will be all zeroes.
01.04.2022 06:17
Let the sequence be $-1007,-1006,\ldots,1007$, and suppose that the first move is made with $x$ and $y$ ($x\ne y$). The two get replaced with $\frac{x+y}2$ and $\frac{x+y}2$. Let the symmetric procedure on a sequence of real numbers be defined as replacing each pair $(a,-a)$ such that $a,-a$ are both in the sequence with $(0,0)$. If $x+y=0$ we end up with $0,0$ in place of $x,y$, we can do the symmetric procedure to obtain all zeroes. If $xy=0$, WLOG $y=0$ (then $x\ne0$). Then do the symmetric procedure to obtain $2k+1$ zeroes ($k\ge0$) and $\frac x2,\frac x2,-x$. Then make the next move with $-x$ and $0$ to get $-\frac x2,-\frac x2,\frac x2,\frac x2$ along with $2k+1$ zeroes. Applying the symmetric procedure finishes. Otherwise, we can make the next move with $-x$ and $-y$ to get two instances of $\frac{-x-y}2$. Applying the symmetric procedure finishes again.
27.07.2022 04:23
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.
12.03.2023 09:51
Let $k$ be the number of numbers (so we want to show that it is true when $k=2015$). Lemma 1: The sequence $(a,-a,b,-b)$ works for any $a,b$. If the first move is applied to $(a,-a)$ or $(b,-b)$ then it obviously work. If the first move is applied to $(s_1a,s_2b)$, where $s_1,s_2\in \{-1,1\},$ we can then make the second move on the other two numbers. These will create two pairs of opposite numbers, which we can just cancel into all 0s. For example, if $s_1=s_2=1$, then the given move makes it $(a+b)/2,(a+b)/2,-a,-b$, then we make it $(a+b)/2,(a+b)/2,-(a+b)/2,-(a+b)/2$ and then cancel everything. We then claim that the sequence $a,-a,2a,-2a,0$ works for $k=5.$ By Lemma 1, if the first given move does not involve 0, then we can just get it to $0,0,0,0,0$. If the first move involves 0 and $a$, then it becomes $a/2,a/2,-a,2a,-2a$, which we can then move to $a/2,a/2,-a,0,0$ and then to $a/2,a/2,-a/2,-a/2,0$. This is similar if we move 0 and $-a$. If the first move involves 0 and $2a$, then it becomes $a,a,a,-a,-2a$, which will become $a,a,0,0,-2a$ and then $a,a,-a,-a,0$ which clearly works. Therefore, the sequence $a,-a,2a,-2a,0$ works. Claim 2: If $n\geq 2$ and $$0,a,-a,2a,-2a\cdots na,-na$$works, then $$0,a,-a,2a,-2a\cdots (n+1)a,-(n+1)a$$works. Consider cases on where the first move is applied. If the first move does not involve a 0, the either it just gets rid of a negative pair, or it disrupts two negative pairs, in which case by Lemma 1, we can get rid of the two negative pairs that the move involved and then just cancel everything else. Furthermore, if the move does not involve $(n+1)a$ or $-(n+1)a$, then we can just get rid of $(n+1)a$ and $-(n+1)a$ on the very next move and reduce it to the case that we know works. Therefore, the only cases requiring consideration are if the first move involves 0 and one of $(n+1)a$ or $-(n+1)a$. Fortunately, this is not very difficult to deal with. If the first move involves 0 and $(n+1)a$, first cancel all of the other negative pairs, so we get $$0,0,0\cdots 0,\frac{n+1}{2}a,\frac{n+1}{2}a,-(n+1)a$$Then, make this $0,\cdots 0,\frac{n+1}{2}a,\frac{n+1}{2}a,-\frac{n+1}{2}a,-\frac{n+1}{2}a,$ which just cancles out. (There are sufficient 0s as long as $n\geq2$). This works similarly if the first move involves 0 and $-(n+1)a.$ Therefore, starting from $a,-a,2a,-2a,0$ we can just keep slapping on negative pairs with increasing coefficients until we reach 2015 terms, so we are done.
13.03.2023 01:28
We claim the sequence $-1007, -1006, \dots, 1006, 1007$ works. We proceed by casework on the initial move. Case 1: The first move operates on $0$ and $x$ for some $x\ne 0$. Then, both are replaced with $x/2$. Then, operate on $-y$ and $y$ for each $y > 0$ which is not equal to $|x|$; this leaves us with a list of $2012$ $0$'s, $1$ copy of $-x$, and $2$ copies of $x/2$'s. To finish, take one of the $0$'s and operate on it and $-x$, which produces two copies of $-x/2$. Then, we have $2011$ $0$'s and two copies of the pair $(-x/2, x/2)$. Operate on each pair to get $4$ $0$'s, leaving us with only $0$'s Case 2: The first move operates on $-x$ and $x$ for some $x > 0$. Then, both are replaced with $0$. To finish, operate on $-y$ and $y$ for each $y > 0$ which is not equal to $x$. This leaves us with all $0$'s. Case 3: The first move operates on $x$ and $y$ where $x,y\ne 0$ and $x \ne -y$. Then, both are replaced with $\tfrac{x + y}{2}.$ Now, operate on $-x$ and $-y$ to produce two copies of $\tfrac{-x-y}{2}$. Then we have two copies of $\tfrac{x + y}{2}$ and two copies of $-\tfrac{x + y}{2}$, so we have two copies of the pair $(\tfrac{x + y}{2}, -\tfrac{x + y}{2})$, and we can operate on both copies of this pair to obtain $4$ $0$'s. Then, operate on $-z$ and $z$ for all $z > 0$ which is not equal to $\pm x$ or $\pm y$. This leaves us with all $0$'s
13.03.2023 01:57
The sequence $-1007, -1006, \dots, 1006, 1007$ works. Let the initial move be on $a$ and $b$, where $|a|\le |b|$. If $a=-b$, then it is easy to see that we can make the sequence all $0$s by symmetry. If $a=0$, then we can do a move on some $x$ and $-x$, and then do a move on $0$ and $-b$, and then it is easy to see we can make the sequence all $0$s by symmetry. Otherwise, we can do a move on $-a$ and $-b$, and then it is easy to see we can make the sequence all $0$s by symmetry.
26.06.2023 21:17
Sketch: Consider the sequence $1,2,3,…,2015$. Now, we can construct the pairs $(1,2015), (2,2014), (3,2013), … (1007,1009)$. Moreover, suppose the first move swaps $a$ and $b$. Now say none of $a, b$ are $1008$. Then if they belong to the same pair, we average the other pairs. Otherwise, we use the other numbers in their respective pairs. Now let’s say WLOG $a=1008$. Then we can operate with $b, 2016-b, c, 2016-c$ to achieve our final objective.
26.06.2023 21:19
Extension for you all: What are sets of sequences that exhibit this property? Certainly many arithmetic progressions seem to work. Must the sequence necessarily be arithmetic.
07.09.2023 02:12
Note that the sequence -1007, -1006, -1005, ... , 1007 works. No matter what the initial step is, the second step always use the negative of the numbers used in the initial step. If the initial step involves 0 and the second step no longer have 0 to use, simply make a 0 before the second step by combining some n, -n unaffected by the initial step. We can eventually pair up all terms in the sequence into the form k,-k, which we merge pairwise to get a constant sequence with everything zero. Full proof here: https://infinityintegral.substack.com/p/usajmo-2015-contest-review
17.05.2024 19:50
can someone tell me what's wrong with my proof for all sequences?
18.05.2024 21:18
ostriches88 wrote: can someone tell me what's wrong with my proof for all sequences?
/bump
31.12.2024 06:48
Literally what lol. I claim that $\boxed{1, 2, 3, \dots, 2015}$ works. Call $1008$ the center of the sequence. Obviously the sum is preserved so the desired final value is the average. Call the mirror of a number to be its reflection over the center. Call eliminating a number to pair it up with its mirror. If our first move does not contain the center, both numbers are either on the same side of the center or different. If they are on the same side, then eliminate all other terms except the two numbers and their mirrors. Then, pair up the two mirrors and pair the remaining four numbers in the obvious manner to make them all equal to the average. If they are on different sides, elimanate all other terms except the two numbers and their mirrors again. Pair up the two mirrors and pair up the remaining four numbers in the obvious manner to make them equal the average (i.e. the original numbers do NOT go together). If the first move does contain the center, eliminate all other terms except the other number, its mirror, and another arbitrary pair we need to work with. Let them be $n-x, n, n+x, n-a, n+a$ to which our first pair makes it $n-x, n+\frac{x}{2}, n+\frac{x}{2}, n+a, n-a$. Now eliminate the $a$ to get $n-x, n+\frac{x}{2}, n + \frac{x}{2}, n, n \implies n - \frac{x}{2}, n + \frac{x}{2}, n + \frac{x}{2}, n - \frac{x}{2}, n$ from which the finish is clear.
04.01.2025 03:47
Case bash lol. We claim the sequence $\boxed{(-1007, -1006, \dots, -2, -1, 0, 1, 2, \dots, 1006, 1007)}$ works. Define $a_k$ to be the $k^{th}$ term in the sequence, and let $i, j$ be two distinct positive integers such that $i, j \leq 2015$. Let the first move be performed on $a_i, a_j$. Case 1 ($i + j = 2016$) In this case, $a_i$ and $a_j$ are replaced with \[\frac{a_i + a_{2016 - i}}{2} = \frac{a_i - a_i}{2} = 0\]Now, perform the move on $a_k, a_{2016 - k}$ for all $1 \leq k \leq 1007$, $k \neq i, j$. Then, each of a_{k}, a_{2016 - k} is replaced with \[\frac{a_k + a_{2016 - k}}{2} = \frac{a_k - a_k}{2} = 0\]Since $a_{1008} = 0$ already, the entire sequence is now $0$. Case 2 (one of $i, j = 1008$) WLOG, assume $j = 1008$. Then, $a_{1008}$ and $a_{i}$ are replaced with \[\frac{a_i + a_{1008}}{2} = \frac{a_i}{2}\]Perform the move on $a_k, a_{2016 - k}$, for all $k$ such that $1 \leq k \leq 1007$, and $k \neq i, 2016 - i$. Once again, each of a_{k}, a_{2016 - k} is replaced with \[\frac{a_k + a_{2016 - k}}{2} = \frac{a_k - a_k}{2} = 0\]Now, every single term of the sequence except for the terms at indices $1008, i, 2016 - i$ are $0$. Now, pick an arbitrary $l$ not equal to the previous indices. We have that $a_l = 0$. Performing the move on the terms at indices $l, 2016 - i$ replaces them with \[\frac{0 + a_{2016 - i}}{2} = -\frac{a_{i}}{2}\]We now have $4$ terms not equal to $0$, with values of $\frac{a_i}{2}, \frac{a_i}{2}, -\frac{a_i}{2}, - \frac{a_i}{2}$. Do the moves on the opposites to make them zero, so now the whole sequence is $0$. Case 3 (everything else) $a_i$ and $a_j$ are replaced with \[\frac{a_i+a_j}{2}\]by the given move. Now, perform the operation on $a_{k}, a_{2016 - k}$ for all $1 \leq k \leq 1007$, and $k \neq i, j, 2016 - i, 2016 - j$. By similar reasoning in the previous cases, everything is now zero except for the terms at indices $i, j, 2016 - i, 2016 - j$. Now, perform the move on indices $2016 - i, 2016 - j$ to replace them both with \[\frac{a_{2016 - i}+a_{2016 - j}}{2} = \frac{-a_i-a_j}{2}\]Now, there are exactly $4$ numbers not equal to $0$, with values of $\frac{a_i + a_j}{2}, \frac{a_i + a_j}{2}, -\frac{a_i + a_j}{2}, -\frac{a_i + a_j}{2}$. Once again, perform the operation on the opposites, and everything is now $0$. Therefore, we see that no matter what the first move is, there is a sequence of finite moves to make the entire sequence $0$, so we are done.