Combinatoric Proof to show the number of good vectors is at most $\binom{n}{\lfloor n/2 \rfloor}$

Question

If I have $n$ real numbers $a_1,...a_n$ where $|a_i| \geq 1, \forall i$ and $2^n$ vectors (v_1,...v_n) such that $v_i \in \{-1,1\}$ and a "good vector" is if: $$-1 < \sum_{i=1}^n v_i \cdot a_i <1$$ then how should I go about showing that the number of "good vectors" is at most $\binom{n}{\lfloor n/2 \rfloor}$?

Answer 1

Let $V=\{-1,1\}^n$, and say that $v=\langle v_1,\ldots,v_n\rangle\in V$ is good if

$$\left|\sum_{k=1}^nv_ka_k\right|<1\,.$$

Let $G=\{v\in V:v\text{ is good}\}$.

For $v=\langle v_1,\ldots,v_n\rangle\in V$ let $P_v=\{k\in[n]:v_ka_k>0\}$ and $N_v=[n]\setminus P_v$; then

$$\sum_{k=1}^nv_ka_k=\sum_{k\in P_v}|a_k|-\sum_{k\in N_v}|a_k|\,.$$

Let $\alpha=\frac12\sum_{k=1}^na_k$, and note that

$$\sum_{k\in N_v}|a_k|=2\alpha-\sum_{k\in P_v}|a_k|\,.$$

Clearly $v$ is good iff

$$\left|\sum_{k\in P_v}|a_k|-\sum_{k\in N_v}|a_k|\right|<1\,,$$

i.e., iff

$$\left|2\sum_{k\in P_v}|a_k|-2\alpha\right|<1\,,$$

or

$$\alpha-\frac12<\sum_{k\in P_v}|a_k|<\alpha+\frac12\,.$$

Suppose that $u,v\in V$ and $P_u\subsetneqq P_v$, and fix $\ell\in P_v\setminus P_u$. Then

$$\sum_{k\in P_v}|a_k|-\sum_{k\in P_u}|a_k|\ge|a_\ell|\ge 1\,,$$

so at most one of $\sum_{k\in P_u}|a_k|$ and $\sum_{k\in P_v}|a_k|$ is in the interval $\left(\alpha-\frac12,\alpha+\frac12\right)$, and hence at most one of $u$ and $v$ is good.

Let $\mathscr{A}=\{P_v:v\in G\}$; we have just shown that $\mathscr{A}$ is an antichain in the partial order $\left\langle\wp([n]),\subseteq\right\rangle$, and it is an immediate consequence of Sperner’s theorem that $|G|=|\mathscr{A}|\le\binom{n}{\lfloor n/2\rfloor}$.