0

I hope this is not too trivial to be asked here, but here it goes anyway. This is just out of curiosity (regarding a problem with graphs but I have "reduced" it to the problem below:)

Let $S_0={{a_1,a_2,\ldots, a_n}}$ where $0< a_i \leq n$.

Form $S_1$ by adding the two smallest elements of $S_0$, form $S_2$ by adding the two smallest elements of $S_1$, etc.

Let $J$ be the smallest integer such that at least one of the elements of $S_{J+1}$ is greater than or equal to $n$.

I find that $j \leq (n+1)-$ average of the $a_i$'s

works for the $a_i$'s I've tried, although Im not quite sure how to show it. What is a better upperbound for $J$ aside from this.

For example, $S_0={{1, 1, 2, 3, 4}}, S_1 = {{2, 2, 3, 4}}, S_2 = {{3, 4, 4}}, S_3 = {{4, 7}}, S_4 = {{11}}$. So $J=3 < 6-2.2$.

flag
It doesn't work if the initial set has too many 0's. Gerhard "Ask Me About System Design" Paseman, 2012.03.21 – Gerhard Paseman Mar 22 2012 at 4:48
Here is another approach. Try characterizing j and S_j, and then pick an element from S_j and breaking it into two to form S_j-1. Gerhard "Jacobi Didn't Say Think Backwards" Paseman, 2012.03.22 – Gerhard Paseman Mar 22 2012 at 10:41
You're right, it doesn't work with 0's. – Ken Gonzales Mar 23 2012 at 6:51
I think this question is too trivial, I vote to close it. – domotorp Mar 29 2012 at 9:10

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.