The integers $1, 2, 3, \ldots, 2016$ are written on a board. You can choose any two numbers on the board and replace them with their average. For example, you can replace $1$ and $2$ with $1.5$, or you can replace $1$ and $3$ with a second copy of $2$. After $2015$ replacements of this kind, the board will have only one number left on it. (a) Prove that there is a sequence of replacements that will make the final number equal to $2$. (b) Prove that there is a sequence of replacements that will make the final number equal to $1000$.
Problem
Source: 2016 CMO #1
Tags: Sequence
adamov1
10.04.2016 23:18
(a) First perform the moves $2016,2014\to 2015$, then $2015,2015 \to 2015$. We now have the sequence $1,2,3,...,2013, 2015$. We now perform the move $n,n-2 \to n-1$, where $n$ is the largest element of the sequence. We see that this takes the sequence from $1,2,3,...,n-2,n\to 1,2,3,...,n-3,n-1$. Thus this move can be repeated until the sequence becomes $1,2,4$. Then we perform $2,4\to 3$, so our sequence is $1,3$, and we can see that $1,3 \to 2$ finishes.
(b) First perform the moves $2016,2014\to 2015$, then $2015,2015 \to 2015$. We now have the sequence $1,2,3,...,2013, 2015$. We now perform the move $n,n-2 \to n-1$, where $n$ is the largest element of the sequence. We see that this takes the sequence from $1,2,3,...,n-2,n\to 1,2,3,...,n-3,n-1$. Thus this move can be repeated until we have $1,2,3,4,...,1000,1002$. Then we perform the moves $1,3\to 2$, then $2,2\to 2$. So we have the sequence $2,4,5,...,1000,1002$. We now perform the move $n,n+2\to n+1$, This takes the sequence from $n,n+2,...,1000,1002\to n+1,n+3,...,1000,1002$. So we perform this move until we have $n=998$, i.e. the sequence is $998,1000,1002$. Then $998,1002\to 1000$ and $1000,1000\to 1000$ finishes.
The algorithm detailed in part (b) can be generalized to show that we can achieve any integer in $[2,2015]$, and it is not hard to show that $1,2016$ are not achievable. IMHO it would have been a better question to ask which integers can be achieved.
rkm0959
01.08.2016 09:32
(a). First, we can go $\{n, n+1, n+2, n+3 \} \rightarrow \{n, n+2, n+2\} \rightarrow \{n, n+2 \} \rightarrow \{n+1\}$. After that, we can start with $\{n-3, n-2, n-1, n+1\} \rightarrow \{n-3, n-2, n\} \rightarrow \{n-3, n-1\}$. So 1~2016 -> 1~2012, 2014 -> 1~2010, 2012 -> ....... -> 1, 2, 4 -> 1, 3 -> 2. We are okay. (b). Do the same thing backwards, and meet in the middle. 1~2016 -> 2, 4~2016 -> 4, 6~2016 ..... -> 998, 1000~2016 -> 998, 1000~2012, 2014 -> 998, 1000~2010, 2012 -> ..... -> 998, 1000, 1001, 1002, 1004 -> 998, 1000, 1001, 1003 -> 998, 1000, 1002 -> 1000, 1000 -> 1000
Garfield
06.01.2017 23:49
Claim:from numbers in interval $[x,y]$, $y-x\geq 2$ we can get $x+1$ and we can get $y-1$. Proof: To get $x+1$ we simply use operation on $y$, $y-2$ to get $y-1$ and then same operation on $y-1$ and $y-1$ so we have $y-1$ now keep doing operation on numbers in ascending order i.e in next step from $y-1$ and $y-3$ we get $y-2$ and the from $y-2$ and $y-4$ we get $y-3$... from $x+2$ and $x$ we get $x+1$.For second part of claim use same algorithm but in increasing order to get $y-1$. Now back to problem,use second part of claim for a).For part b) use first part of claim so from $[1,999]$ we have $998$, and second part of claim on $[1001,2016]$ to get $1002$ now from $998$ and $1002$ we're done.
jj_ca888
22.06.2020 00:48
a) Replace $(2014, 2016)$ with $2015$, and replace $(2015, 2015)$ with $2015$. You are left with $\{1, 2, \ldots , 2013\} \cup \{2015\}$. Now replace $(2013, 2015)$ with $2014$ to get $\{1, 2, \ldots , 2012\} \cup \{2014\}$. Keep repeating this process until you get to $\{1, 2\} \cup \{4\}$, which upon replacing $(2,4)$ with $3$ and then $(1, 3)$ with $2$, yields our desired result. $\blacksquare$ b) Part a) actually gives us quite a good setup for solving Part b). We can apply Part a) on the set $\{1001, 1002, \ldots 2016\}$ to get $1002$. Similarly, we apply the reverse operation of Part a) on set $\{1, 2, \ldots 999\}$ to get $1000$. Thus, we are left with the three element set $\{998, 1000, 1002\}$ which easily yields our desired final number $1000$. $\blacksquare$ Remark: Darn what a troll :/
PCChess
16.04.2021 03:36
A. Let $(x,y)$ denote the replacement of two integers $x,y$. First do $(2014, 2016)$, resulting in $2015$. Then do $(2015,2015)$. The remaining integers are $1, 2, \dots, 2013, 2015$. Now do $(2013, 2015)$ to make the integers $1, 2, \dots 2012, 2014$. Do $(2012, 2014)$ and continue this process, each time taking the average of the largest and second largest (which is always 2 less than the largest) integer. Eventually, the remaining numbers are $1, 2, 4$. Performing $(2, 4)$ and then $(1, 3)$ makes the final number equal $2$. B. Do $(1, 3)$ and $(2,2)$, so the remaining numbers are $2, 4, 5, 6, \dots$. Do $(2,4)$ and then $(3,5)$, each time taking the smallest two numbers until the numbers become $998, 1000, 1001, \dots$. Now we do the similar process but starting with $(2016, 2014)$ and $(2015, 2015)$. Each time we replace the two largest integers until the remaining integers become $998, 100, 1002$. Doing $(998, 1002)$ and $(1000, 1000)$ finishes.
Mogmog8
08.06.2022 08:19
(a) Let $(a,b)\mapsto c$ denote replacing $a$ and $b$ with $c.$ Notice \begin{align*}(2016,2014)\mapsto 2015,&(2015,2015)\mapsto 2015,\\&(2015,2013)\mapsto 2014,(2014,2012)\mapsto 2013,\dots,(3,1)\mapsto 2\end{align*}leaves only $2$ on the board. (b) First, we use the technique from (a) to leave only the numbers $1,2,\dots,999,1000,1002$ on the board. Then, \begin{align*}(1,3)\mapsto 2,(2,4)\mapsto 3,\dots,(997,999)\mapsto 998\end{align*}leaves only $998,1000,$ and $1002$ on the board. From here, $(998,1002)\mapsto 1000,(1000,1000)\mapsto 1000$ finishes. $\square$
bjump
06.04.2023 00:42
(a) Consider this use of the algorithm: $n,n+1, n+2, n+3 \mapsto n, n+2, n+2 \mapsto n, n+2 \mapsto n+1$ and $n-4, n-3, n-2, n-1, n+1 \mapsto n-4, n-3, n-2, n \mapsto n-4, n-2, n-2 \mapsto n-4,n-2 \mapsto n-3$ This shows that if we start at with set {1, 2, ..., 2016} we can take out sets of 4 until we reach the bottom where we will have a two left over. (b)We can do this backwards and forwards from each end to get to $1000$ since $1000 \equiv 2 \pmod{4}$