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
    Commented 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
    Commented 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
    Commented Mar 3, 2015 at 21:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .