Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|cite|improve this question
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 '12 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 '12 at 10:41
You're right, it doesn't work with 0's. – Ken Gonzales Mar 23 '12 at 6:51
I think this question is too trivial, I vote to close it. – domotorp Mar 29 '12 at 9:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.