There exists a vector $c\in C$ with $c\cdot b=1$

Let $n$ be a positive integer, and $A$ be the set of all non-zero vectors of the form $(e_1,e_2,\dots,e_n)$, where $ e_i\in\{0,1\}$. So $|A|=2^n-1$. Let $B$ be a proper subset of $A$. Does there always exists a subset $C\subseteq A$ of size at most $n-1$ such that for any vector in $b\in B$, there exists a vector $c\in C$ with $c\cdot b=1$?

If we were to allow $B=A$, then we can choose a set $C$ of size $n$ to be the unit vectors $(1,0,\dots,0),(0,1,\dots,0),\dots,(0,0,\dots,1)$. Now, since we have $B$ is a proper subset of $A$, it seems we should also need a smaller $C$.

Solutions Collecting From Web of "There exists a vector $c\in C$ with $c\cdot b=1$"

Sure. We basically use a missing vector to define things in a way that saves us 1 member of $C$.

More formally, let $u$ be a vector missing from $B$, $S$ be the support of $u$, and let $v_i$ be the vector which has only one $1$ in the $i$-th position. Then define $C$ as follows:

  • include in $C$ all vectors $v_i$ for $i\notin S$;
  • fix some $s\in S$, and include in $C$ all vectors of the form $v_s + v_j$ where $j\in S-\{s\}$.

This gives a total of $|C|=n-1$ elements. Now let $v\in B$ be any vector. If $v_i=1$ for some $i\notin S$, we can just use $v_i\in C$. Otherwise, the support of $v$ is a subset of $S$. If $v_s\neq 1$, there will be some $j$ such that $v_j=1$ and we can use $v_s+v_j\in C$.

Otherwise, $v_s=1$; this is the key step: this means there will be $j\in S$ such that $v_j=0$, since otherwise $v=u$. Thus, we can use $v_s+v_j\in C$.

This covers all cases and completes the analysis.