# Showing that the strategy of picking the adjacent numbers from last leads to minimum value at last

Numbers 1,2,3,…n(each integer from 1 to n once) are written on a board. In one operation you can erase any two numbers a and b from the board and write one integer (a+b)/2 rounded up instead. What is the minimum number which one can get left after carrying out the operation n-1 times for a given n>=2 ?

My progress Suppose we have k numbers that is from 1 to k , now we know that when we do average and round it up to closest integer it will be lying between the chosen a and b integers (inclusive of both). so we need to make sure that we always get the average number closest to a ,one way would be taking k-1 and k and averaging repeating it again . this probably gives the number as 2 . But what is the proof that this is the optimal strategy which gives the minimum number of 2 always ? (expect a algebraic solution using inequalities or maybe some bounds ) i am not able to think how to show that since initial numbers we chose can be any .

Ross gave a clue like maybe prove that at each step you decrease the sum of all the numbers as much as possible so your greedy algorithm must be optimal. using that i believe i got it maybe:

Consider the sum 1+2+3+4+5+6... +n; at each step we try to decrease the sum as much as possible so we need to take some numbers from last . as intial will not cause much decrease , hence we will consider the n-1 and n, that will decrease the sum by n-1,similarily we will consider next step of maximum decrease by taking the last two again in the sum: that is n-2,n, it will cause decrease of n-1, next n-3,n-1 and the post continues . so since our algo is making the max decrease at each time . thats why it should be the optimal .

• For some basic information about writing mathematics at this site see, e.g., here, here, here and here. Jun 10 at 13:49
• thanks i will try to follow that format @AnotherUser Jun 10 at 14:39
• Your max decrease doesn’t work because it’s maybe possible to do a lower increase in an earlier round which allows you to do a larger increase in a later round. Showing that greedy is optimal can be difficult.
– Eric
Jun 10 at 17:12
• an example please @Eric Jun 10 at 18:05
• 1235. If you do 12 then 35, you’ll reduce the sum by 4 on the second draw. If you do 35 then 24, you’ll reduce the sum by 3 (i.e. less) on the second draw. I agree that greedy happens to work out, but proving it’s the only option seems tricky. My proof below showed it’s the best option overall.
– Eric
Jun 10 at 18:10

Let $$n\geq 2$$. You need to show two things. First, that it’s possible to attain $$2$$ and that it’s impossible to do better.

Let’s show by induction that if I have $$1,2,…,k-2,k$$ that I can get down to $$2$$. When $$k$$ is $$3$$, I have $$1,3$$, which gives $$2$$. If I have $$1,2,…,k-2,k-1,k+1$$, combining the top two gives $$1,2,…,k-2,k$$, which by the inductive hypothesis leads to $$2$$.

Going back to the original problem, if $$n=2$$, then combining $$1$$ and $$2$$ gives $$2$$. For $$n\geq 3$$, if I then have $$1,…,n$$, combining the top two leaves $$1,2,…,n-2,n$$ which by the above leads to $$2$$.

As Ross notes, you have to be careful to always choose the largest two numbers not just any two adjacent numbers. There’s very little leeway here.

Now, let’s show that $$2$$ is optimal. Note that the combination is always at least as large as the minimum of its two predecessors, so the minimum will never go below $$1$$. Note also that if $$b\geq 2$$ then $$(a+b)/2\geq (1+2)/2=1.5$$, so $$\lceil (a+b)/2\rceil\geq 2$$, so combining something greater than $$2$$ with anything else will always remain greater than $$2$$. Thus, since there are elements that are greater than $$2$$ initially and combining them will never completely remove them, then the final number after all combinations must be at least $$2$$.

• A typo? Missing $k$ in "combining the top 2 gives $1,2,...,k-2,k$ which by the induction hypothesis etc Jun 10 at 14:03
• Yes, typo, thanks.
– Eric
Jun 10 at 14:21
• what about k-1? you didnt consider that from start ? in the induction step base case and too in induction step Jun 10 at 16:37
• also you are considering just 1and 2 and taking average it might be that we may choose numbers other than 1 and 2 in the last proving step Jun 10 at 16:57
• yes, 1,2 is it’s own case. The issue is that the original problem isn’t inductive, so you can first combine the top two, and then apply induction on 1,2,…,n-2,n to get it down to 1,3 and then 2
– Eric
Jun 10 at 17:10

It does not. If you start with $$123456$$ and take the smallest neighboring pair you go $$123456, 23456, 3456, 456, 56, 6$$ but if you start down from the top and try to avoid rounding you go $$123456, 12355, 1235, 124, 13, 2$$

• my bad i mean from top only Jun 10 at 14:36
• You should edit that into the question. Maybe you can prove that at each step you decrease the sum of all the numbers as much as possible so your greedy algorithm must be optimal. Jun 10 at 15:12
• good point will try it Jun 10 at 16:42
• may you check if its right ? and if its wrong please give a way Jun 10 at 18:04
• You need to show that the decrease of the sum is greatest with this selection. I believe that works, but the inductive argument of Eric is clear Jun 10 at 21:48