3
$\begingroup$

Given numbers $0 \leq d_i \leq 1$ for $i=1,\ldots,m$, it is easy to see that you can always find signs $\varepsilon_i \in \{-1,1\}$ such that the partial sums $\sum_{i=1}^k \varepsilon_i d_i/2$, for $k=0,\ldots,m$(where $\sum_{i=1}^0 = 0$) lie in an interval of size at most 1. Is this best possible? i.e. is there a choice of $m$ and $d_i$ such that for any choice of signs the strip must be of size at least 1-$\delta$?

Such an example for $\delta = 1/4$ is to take $m = 3$, $d_1 = 1 = d_3$ and $d_2 = 1/2$. What about for smaller $\delta$?

Improve this question
$\endgroup$
1
  • $\begingroup$ How can one see that for $\: m = 1 \:$ and $\: d_1 = -3 \;$? $\;\;\;\;$ $\endgroup$
    – user5810
    Mar 4, 2015 at 1:50

1 Answer 1

Reset to default
5
$\begingroup$

Of course, this is best possible. Choose $d_{2k-1}=1$, $d_{2k}=1-\delta$ for $k=1,2,\dots$. If two consecutive signs are the same, we already have two partial sums on a distance $(2-\delta)/2$. If signs alternate, partial sums tend to infinity (actually, we need $m=O(1/\delta)$ for getting too large partial sum).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I came up with a similar (counter)example for a related problem, but didn't realize you could also apply it here. Is it possible that these are the 'only' bad examples? It is not obvious to me what 'only' should mean, so I understand this question is not very clear. $\endgroup$
    – funda
    Mar 3, 2015 at 21:48
  • $\begingroup$ In which sense the only? We may add any set of $d$'s in any place, for example $\endgroup$
    – Fedor Petrov
    Mar 3, 2015 at 21:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.