Prove that there exists a constant $0<c \leq 1$ such that, if we put $2^{n}$ distinct closed unit balls in $\mathbb{R}^{n}$, each centered at $\{-1,1\}^{n}$, then every hyperplane containing the origin intersects at least $c$ fractions of them (i.e., $c \cdot 2^{n}$ balls).
I attempted to write the hyperplane as $\sum_{i=1}^{n} a_{i} x_{i}= 0, \sum a_{i}^{2}=1$ and tried to bound the probability that $|\sum_{i=1}^{n} a_{i} y_{i}|\geqslant t, y_i = \pm 1, t = \max |a_i|$. It seems that the probability is $1$ so no useful bounds could be found by this way. Maybe grouping the points work? I'm not sure how to proceed.
Thanks for your help.
The problem is solved, with a loose bound.
WLOG, let the hyperplane be $a^\top x = 0, \|a\| = 1, a_1\geqslant a_2\geqslant \cdots \geqslant a_n \geqslant 0$. We have $a_i\leqslant \frac{\sqrt{2}}{2}, \forall i\geqslant 2$. Let $m$ be the smallest integer that \begin{align*} \left| \sum_{i=2}^m a_i^2\right. &\left. - \sum_{i=m+1}^n a_i^2 \right| \leqslant 1/2\\ A &= \sum_{i=2}^m a_i^2\\ B &= \sum_{i=m+1}^n a_i^2 \end{align*} And we have the relationship that $a_1^2 + A + B = 1$.
Let r.v. $X = \sum_{i=1}^n a_i\epsilon_i, Y= \sum_{i=2}^m a_i\epsilon_i, Z = \sum_{i=m+1}^n a_i\epsilon_i$
Then $\mathbb{E} Y = \mathbb{E} Z = 0, \mathrm{Var}\ Y = A, \mathrm{Var}\ Z = B$.
Using Chebyshev's inequality, we have \begin{align*} \mathbb{P} (|Y-\mathbb{E} Y| \leqslant 1) \geqslant 1-A\\ \mathbb{P} (|Z-\mathbb{E} Z| \leqslant 1) \geqslant 1-B \end{align*} Using the symmetry of $Y$ and $Z$, we get \begin{align*} \mathbb{P} (0\leqslant Y\leqslant 1) \geqslant (1-A)/2\\ \mathbb{P} (-1\leqslant Z\leqslant 0) \geqslant (1-B)/2 \end{align*} So \begin{align*} \mathbb{P} (|X|\leqslant 1) &\geqslant P(|Y+Z|\leqslant 1, \epsilon_1 = -\mathrm{sgn} (Y+Z))\\ &= \frac{1}{2}\mathbb{P}(|Y+Z|\leqslant 1)\\ &\geqslant \frac{1}{2}\mathbb{P}(0\leqslant Y\leqslant 1, -1\leqslant Z\leqslant 0)\\ &\geqslant \frac{1}{8}(1-A)(1-B)\\ &\geqslant \frac{1}{8}(a_1^2 + B)(a_1^2 + A)\\ &=\frac{1}{8}\left(\frac{a_1^2}{2} + B\right)\left(\frac{a_1^2}{2} + A\right)\\ &\geqslant \frac{1}{8}\cdot \frac{1}{4}\cdot \frac{3}{4}\\ &\geqslant \frac{3}{128} \end{align*} Which means at least $\frac{3}{128} \cdot 2^n$ balls intersect with the random hyperplane.