The answer is that *n* hyperplanes are required.

Consider some set of hyperplanes that cover the 2^{n}-1 desired
points but not the origin. These can all be represented by equations of the
type

The affine element can safely be taken to be "+1" as in the equation above, because we know the planes do not cross the origin.

Now, let us multiply all these equations together. If there are *k*
equations, the result will be a polynomial of degree *k*. Because we know
all points in the hypercube other than the origin are covered by the
hyperplanes, the value of the polynomial will be zero at each of them. In
the origin itself the polynomial has the value 1, as can be ascertained
by substituting in the values *x _{i}*=0 into every hyperplane
equation.

Now comes the trick: in every monomial of
the polynomial, replace every occurrence of
*x*_{i}^{j} by *x*_{i}.
Notably, the values of the polynomial in all hypercube points will not have
changed because of this, because both 0^{j}=0 and
1^{j}=1. Note also that the degree of this new polynomial
is necessarily at most *k*.

The new polynomial is easier to handle than the original one, in that we know
that it is multilinear: in every monomial, every variable appears with
degree at most 1. This makes the total number of monomials at most
2^{n}. Furthermore, it is not difficult to see that the
values of the polynomial at the hypercube points determine the values of the
polynomial's coefficients uniquely: one can simply solve for them, starting
with the value of the free coefficient (from the polynomial's value at the
origin), continuing with the value of the linear coefficients (from the
polynomial's values at the points whose coordinate sum is 1) and continuing in
this way, each time incrementing the degree of the monomials solved for and
the sum of the point coordinates.

In fact, the multilinear polynomial is the polynomial whose coefficients are
(-1)^{d}, where *d* is the degree of the monomial.

The important feature of this polynomial is that the coefficient of its
degree *n* monomial is nonzero, meaning that the polynomial itself is
of degree *n*. We have seen that this degree is necessarily at most
*k*, so we have *k*≥*n*, a lower bound on the number of
hyperplanes needed.

Actually finding a solution with *k*=*n* is easy. One can pick,
for example, *x _{i}*=1 for all

The methodology used in this solution is known as the "arithmetical method". It has since been used to attack many fundamental problems in combinatorics.

*Happy birthday, Noga!*