0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ It doesn't work if the initial set has too many 0's. Gerhard "Ask Me About System Design" Paseman, 2012.03.21 $\endgroup$ Mar 22, 2012 at 4:48
  • $\begingroup$ 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 $\endgroup$ Mar 22, 2012 at 10:41
  • $\begingroup$ You're right, it doesn't work with 0's. $\endgroup$ Mar 23, 2012 at 6:51
  • $\begingroup$ I think this question is too trivial, I vote to close it. $\endgroup$
    – domotorp
    Mar 29, 2012 at 9:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.