95 vectors in a cube (APMC 1995)

Question

Let $C$ denote the cube $[-1,1] \times [-1,1] \times [-1,1]$. Let $v_1,v_2,...,v_{95}$ be points (treated as vectors from the origin to these points) inside or on the boundary of $C$. Consider the set $W$ of $2^{95}$ vectors of the form $s_1v_1+s_2v_2+...+s_{95}v_{95}$ where each $s_i=1$ or $-1$.

(a) If $d=48$, then show that there exists a vector $w=(a,b,c)$ in $W$ such that $a^2+b^2+c^2 \le d$.

(b) Does there exist $d<48$ that satisfies (a)?

(c) What is the smallest value of $d$ that satisfies (a)?

Source : Austrian-Polish Mathematical Competition 1995 Problem 8

Generalisation : If we have $n$ vectors $v_1,v_2,...,v_n$ instead and consider $2^n$ vectors of the form $s_1v_1+s_2v_2+...+s_n v_n$ where $s_i=1$ or $-1$, what is the smallest number $d=d_n$ such that there is a vector $w=(a,b,c)$ in $W$ st $a^2+b^2+c^2 \le d$? At least what is a good upper bound for $d_n$?

Attempt (for the generalisation) :

Since $\sum_{s_i=\pm 1} \left|\sum_{j=1}^n s_jv_j\right|^2=2^n \sum_{j=1}^n|v_j|^2$ and $|v_j|\le \sqrt 3$, it follows that for $d\ge 3n$, there exists $w\in W$ st $|w|^2\le d$. I don't see how to improve this bound.

Answer 1

Lemma: If $v_1, \dots, v_5$ are five vectors in the cube $C = [-1, 1]^3$, then there exist two indices $1\leq i < j \leq 5$ and $s, t \in \{-1, 1\}$ such that $s v_i + t v_j \in C$.

Proof: We cut the cube $C$ into eight small cubes: $[0, 1] \times [0, 1]\times [0, 1]$, $[-1, 0] \times [0, 1] \times [0, 1]$ ... etc.

Two small cubes are called "opposite to each other" if they are images of each other with respect to the symmetry around the origin. E.g. $[0, 1] \times [0, 1] \times [0, 1]$ is opposite to $[-1, 0] \times [-1, 0] \times [-1, 0]$.

The eight small cubes then form four groups, each group being two small cubes that are opposite to each other.

Since we have five vectors, there are two of them that lie in the same group, say $v_i, v_j$. If they live in the same small cube, then $v_i - v_j$ is in $C$; otherwise, they live in opposite small cubes, and $v_i + v_j$ is in $C$.

---

Lemma: If $n > 4$ and we have $n$ vectors $v_1, \dots, v_n \in C$, then there exists $n - 1$ vectors $w_1, \dots, w_{n - 1} \in C$ such that the set $\{\sum_i t_i w_i: t_i \in \{-1, 1\}\}$ is a subset of $\{\sum_i s_i v_i: s_i \in \{-1, 1\}\}$.

Proof: We apply the previous lemma to $v_1, \dots, v_5$. Without loss of generality, assume that $sa_1 + ta_2$ is in $C$, with $s, t \in \{-1, 1\}$. Then it suffices to choose $w_1 = sa_1 + ta_2, w_2 = a_3, w_3 = a_4, \dots$.

---

Lemma: If $n \geq 4$ and we have $n$ vectors $v_1, \dots, v_n \in C$, then there exists $4$ vectors $w_1, \dots, w_4\in C$ such that the set $\{\sum_i t_i w_i: t_i \in \{-1, 1\}\}$ is a subset of $\{\sum_i s_i v_i: s_i \in \{-1, 1\}\}$.

Proof: Use the previous lemma and induction on $n$.

---

Now it is enough to use your argument (applied to $n = 4$) to conclude that $d = 12$ works for any $n \geq 4$.