Intersection of the corners of a hypercube and a hyperplane

Question

Consider the corners $c$ of a unit hypercube in $\mathbb{R}^n$ (for example in $\mathbb{R}^2$, $c = \{\{0,0\},\{1,0\},\{0,1\},\{1,1\}\}$) and a hyperplane $p \subseteq \mathbb{R}^{n-1}$ (for example in $\mathbb{R}^{2-1},$ $ p $ is a line). How do I prove that the hyperplane $p$ intersects at most half of the corners of the hypercube? Geometrically it seems obvious, but I'm not sure how to show this rigorously.

Answer 1

Let $$p = \{x \in \mathbb{R}^n \mid a^Tx = \delta\}, \ \text{for some $\delta \in \mathbb{R}$ and nonzero $a \in \mathbb{R}^n$}$$ be a $(n-1)$-dimensional hyperplane. The intersection is then the set $$c \cap p = \{x \in \{0,1\}^n \mid a^Tx = \delta\}.$$

Since $a^Tx = \sum_{i=1}^n a_i x_i$ where $x_i$ is either $0$ or $1$, every $x \in c \cap p$ corresponds to a subtuple of $a = (a_1, \dotsc, a_n)$ whose entries sum to $\delta$ (where $x_i = 1$ if and only if $a_i$ is in the subtuple). So we count the number of ways in which we can form subtuples of $a$ that sum to $\delta$. This is an elementary combinatorial argument:

Lemma. Let $a = (a_1, \dotsc, a_n) \in \mathbb{R}^n$ be a nonzero vector, and let $\delta \in \mathbb{R}$. There are at most $2^{n-1}$ subtuples $(a_{i_1}, \dotsc, a_{i_k})$ of $a$ whose sum is $\delta$.

Proof. True for $n=1$. (There are exactly two subtuples of $a$, namely the empty tuple and $a$ itself. If $\delta = 0$ then since $a$ is nonzero only the empty tuple sums to $\delta$, while if $\delta \neq 0$ then only $a$ may sum to $\delta$.)

Let $n > 1$ and consider $a = (a_1, \dotsc, a_n) \in \mathbb{R}^n$. We have two cases:

1. $(a_1, \dotsc, a_{n-1}) = 0$. Then $a_n \neq 0$. If $\delta \neq a_n$ then no subtuples sum to $\delta$. If $\delta = a_n$ then the tuples $(s, a_n)$ sum to $\delta$ where $s$ is any subtuple of $(a_1, \dotsc, a_{n-1})$, and there are exactly $2^{n-1}$ of these. In either case the bound holds.

2. $(a_1, \dotsc, a_{n-1}) \neq 0$. By the induction hypothesis at most $2^{n-2}$ subtuples of $(a_1, \dotsc, a_{n-1})$ sum to $\delta$, and at most $2^{n-2}$ sum to $\delta - a_n$, so that at most $2\cdot2^{n-2} = 2^{n-1}$ subtuples of $a$ sum to $\delta$.

The result for hyperplanes and vertices of the hypercube follows immediately since $c$ has cardinality $2^n$.