2
$\begingroup$

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 .

$\endgroup$
6
  • $\begingroup$ For some basic information about writing mathematics at this site see, e.g., here, here, here and here. $\endgroup$
    – Another User
    Jun 10 at 13:49
  • $\begingroup$ thanks i will try to follow that format @AnotherUser $\endgroup$
    – coder1229
    Jun 10 at 14:39
  • $\begingroup$ 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. $\endgroup$
    – Eric
    Jun 10 at 17:12
  • $\begingroup$ an example please @Eric $\endgroup$
    – coder1229
    Jun 10 at 18:05
  • $\begingroup$ 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. $\endgroup$
    – Eric
    Jun 10 at 18:10

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ A typo? Missing $k$ in "combining the top 2 gives $1,2,...,k-2,k$ which by the induction hypothesis etc $\endgroup$
    – Peter
    Jun 10 at 14:03
  • $\begingroup$ Yes, typo, thanks. $\endgroup$
    – Eric
    Jun 10 at 14:21
  • $\begingroup$ what about k-1? you didnt consider that from start ? in the induction step base case and too in induction step $\endgroup$
    – coder1229
    Jun 10 at 16:37
  • $\begingroup$ 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 $\endgroup$
    – coder1229
    Jun 10 at 16:57
  • $\begingroup$ 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 $\endgroup$
    – Eric
    Jun 10 at 17:10
1
$\begingroup$

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$

$\endgroup$
6
  • 1
    $\begingroup$ my bad i mean from top only $\endgroup$
    – coder1229
    Jun 10 at 14:36
  • $\begingroup$ 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. $\endgroup$
    – Ross Millikan
    Jun 10 at 15:12
  • $\begingroup$ good point will try it $\endgroup$
    – coder1229
    Jun 10 at 16:42
  • $\begingroup$ may you check if its right ? and if its wrong please give a way $\endgroup$
    – coder1229
    Jun 10 at 18:04
  • $\begingroup$ 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 $\endgroup$
    – Ross Millikan
    Jun 10 at 21:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .