Suppose we have a hyperplane H in $\mathbb{R}^n$ and a set of points S = $\{0,1\}^k,\; k\leq n $.
We want to find the maximum number of points that the hyperplane H can contain from the set S.
edit: An element $s\in S$ is represented in $\mathbb{R}^n$ as an ordered tuple where first $n-k$ values are all 0 and remaining $k$ values are specified by $s$.
Ex: The maximum number of points for $k=2$ and $n=2,3$ is 2 and 4.
Explanations with intuition and references are highly appreciated. Thanks.
Let $S_k = \{0, 1\}^k \times \{0\}^{n - k}$. If $k < n$, then the entirety of $S_k$ lies in the hyperplane $$\{(x_1, \ldots, x_n) \in \Bbb{R}^n : x_n = 0\}.$$ This should make sense, as a $k$-dimensional array can fit inside a $k$-dimensional subspace, which can fit inside an $(n-1)$-dimensional affine subspace (i.e. a hyperplane), provided $k \le n - 1$. So, the maximum is $2^k$ in this case.
If $k = n$, then the answer is $2^{n - 1}$. To prove this, suppose we have a subset $D \subseteq S_n$ such that $D$ is a subset of some hyperplane $H$.
Call a pair of points $x, y \in S_n$ $i$-opposite, for $i = 1, \ldots, n$, if $x_j = y_j$ if and only if $j \neq i$, i.e. $x - y = \pm e_i$ where $e_i$ is the $i$th standard basis vector. Note that, for each point $x$, there is a unique $p_i(x) \in S_n$ so that $x, p_i(x)$ are $i$-opposite (i.e. $p_i(x)$ agrees with $x$ in every coordinate except the $i$th one). Note that $p_i$ is a bijection on $S_n$ and $p_i^2$ is the identity function
Now, note that we cannot have $i$-opposite pairs or all $i$, because this would imply that the $(n-1)$-dimensional subspace $H - H$ contains all $n$ standard basis vectors, which would imply $H - H = \Bbb{R}^n$. So, there is some $i$ so that $D$ does not admit any $i$-opposite pairs, i.e. $x \in D \implies p_i(x) \notin D$.
Thus, $p_i(D) \subseteq S_k$ is disjoint from $D$. Note also that, since $p_i$ is a bijection, $|p_i(D)| = |D|$. Thus, $$2^n = |S_n| \ge |p_i(D) \cup D| = |p_i(D)| \cup |D| = 2|D| \implies |D| \le 2^{n - 1},$$ as required.