show/hide this revision's text 4 deleted 7 characters in body; added 1 characters in body

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 Ive 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}} $4}}, S_1 = {{2, 2, 3, 4}}$ $4}}, S_2 = {{3, 4, 4}}$ $4}}, S_3 = {{4, 7}}$ $7}}, S_4 = {{11}}$. So $J=3 < 6-2.2$.
show/hide this revision's text 3 no more zeroes

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\leq 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 Ive 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$.
show/hide this revision's text 2 tried to edit the braces but they're not showing up. anyway, all the S_i's are sets; added 1 characters in body

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\leq 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 $(n+1)-$ j \leq (n+1)-$ average of the $a_i$'s

works for the $a_i$'s Ive 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$.
show/hide this revision's text 1