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 .
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$.