Let $A\in \mathbb R^{n\times n},\ b\in \mathbb R^n$ such that $\forall x\in \{-1,1\}^n : Ax\ne b$.

Let us denote: $S=\{x\in\mathbb R^n|Ax=b\}$ ('S' for solution set).

Is $\ \#\Big\{H\in\big\{ \{-1\}, \{1\}, (-1,1)\big\}^n \ \Big|\ H\cap S\ne\emptyset\ \Big\} = O(n)$?

where '#' denotes the cardinality of the set.

My intuition tells me that this should be true, but I can't figure out how to prove or disprove it.

So far, I've done many trial and error "experiments" that also support my conjecture, but I am stuck in proving/ disproving it in the general case.

By the way, it is easy to see that WLOG the solution set is a hyper-plane. So, we can modify $S$ to be $S=\{x\in\mathbb R^n|a^T x=b\}$ for $a\in\mathbb R^n, b\in\mathbb R$ such that $\forall x\in \{0,1\}^n:a^T x\ne b$.