The answer is that n hyperplanes are required.
Consider some set of hyperplanes that cover the 2n-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 xi=0 into every hyperplane equation.
Now comes the trick: in every monomial of the polynomial, replace every occurrence of xij by xi. Notably, the values of the polynomial in all hypercube points will not have changed because of this, because both 0j=0 and 1j=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 2n. 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, xi=1 for all i=1,...,n or, as another example, Σ xi=d for d=1,...,n.
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!
Back to riddle
Back to main page