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