Finding a bound on a certain number of sums Let $x_1, ..., x_{2n}$ be real numbers with $|x_i
| ≥ 1$ for all $i$, and let $I ⊂ R$ be an
arbitrary open interval of length $2$. I want to:
(a) Prove that the number of sums $\sum_{i=1}^{2n}ε_ix_i$
, where $ε_i ∈ \{−1, +1\}$, which fall in the interior
of $I$ does not exceed $\binom{2n}{n}$.
(b) Show that for a closed interval $I$ of length $2$ the statement is not necessarily true.
I can't see why binomial coefficients come into the picture when we are dealing with intervals. I thought we could try a proof by contradiction; assume that the number of sums is greater than $\binom{2n}{n}$, and find a contradiction. But I cannot see what true statement would be contradicted.
 A: Welcome to MSE!
First, some intuition on where the binomial coefficient might come from. We think of your problem as standing at $0$ on the real line, then we're gracelessly flung either left or right by $x_i$ units. At the next timestep, we're again flung left or right, but now by $x_2$ units. We get tossed around $2n$ times, and we want to know whether or not we end up inside some target set $I$.
Obviously the simplest case of this problem is when each $x_i = 1$, and our target set is $I = (-1,1)$. In this case, we want to know how we can possibly end up back at $0$, and the answer is clear! We had better move left and right the same number of times, so that our net amount of movement cancels out. Of course, that means we have $2n$ many timesteps, and we want to choose $n$ of them to be rightwards moving (forcing the other $n$ to be leftwards moving). So we see there are $\binom{2n}{n}$ many ways this can happen.
But this also shows us how we can solve part (b). After all, when $I = [-1,1]$ it should be easier to hit $-1$, $0$, or $1$ than it is to just hit $0$, right? And indeed, I'll leave it as an easy exercise that for $I = [-1,1]$ with $x_1 = x_2 = x_3 = 1$ and $x_4 = 2$, we can hit the target more than $\binom{4}{2} = 6$ times.
Now, what about part (a)?
Intuitively, since our interval has width $2$ and each of the $x_i$ is at least $1$, it's hard to stay inside of $I$ for too long. After all, if we start inside $I$ then each time we get thrown around, at most one choice will have us stay inside $I$. Somehow when the $x_i$ are big compared to the target, it's easy to "overshoot". However, if one of our $x_i$ is small compared to the target, then it's easy to intuit that we can stay inside the target for longer.
If we're feeling optimistic, we might try to turn this intuition into a proof idea: Maybe if too many of the sums stay inside of $I$, it's because at least one of the $x_i$ was small!
This turns out to be true, and with some experimentation, you're likely to guess the reason yourself, even if you don't know about Sperner's Theorem (as hinted at in the comments). Since we do know, though, I'll present a clean proof citing this theorem, but you should think about how you might have realized you needed something like sperner's theorem, even if you didn't know it existed! One way to do this might be to work through some concrete examples with this proof in mind.

First, we'll assume that all the $x_i$ are positive. Obviously this doesn't change things, since changing the sign of $x_i$ doesn't change which sums are possible, it just swaps the roles of $\epsilon_i = \pm 1$ in getting to a particular sum.
Say we have more than $\binom{2n}{n}$ choices of signs that land inside $I$. If we identify a sequence $(\epsilon_i)$ with the subset $\{ i \mid \epsilon_i = +1 \}$, then we have more than $\binom{2n}{n}$ subsets of $[2n]$, so by sperner's theorem we see that we must have two sets $A$ and $B$ with $A \subset B$ so that both of the following sums land in $I$:
$$\sum \epsilon_i^A x_i = \sum_{i \in A} x_i - \sum_{i \in A^c} x_i$$
$$\sum \epsilon_i^B x_i = \sum_{i \in B} x_i - \sum_{i \in B^c} x_i$$
Now using $A \subset B$, we subtract these two sums to see
$$\sum \epsilon_i^B - \sum \epsilon_i^A = 2 \sum_{i \in B \setminus A} x_i$$
Since both sums were inside $I$, they must have been within $2$ of each other! That is,
$\left \lvert \sum \epsilon_i^B - \sum \epsilon_i^A \right \rvert < 2$, so that $\sum_{i \in B \setminus A} x_i < 1$. But since each $x_i$ is positive, this means the $x_i \in B \setminus A$ must all be less than $1$, as desired!

I hope this helps ^_^
