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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.