# Vectors inside the unit hypercube.

The following problem has been bothering me for a while, and I finally gave up to solve it on my own. However, I still would like to see a solution:

For an arbitrary integer $n$ consider a set of all n-vectors with coordinates $1$ and $-1$, e.g. for $n=2$:

$(1,1),\ (1,-1),\ (-1,1),\ (-1,-1)$

The sum of the vectors is obviously $0$ (zero-vector). Now, arbitrarily change some of the coordinates to 0 (it may be different coordinates in different vectors), e.g.:

$(0,1),\ (1,0),\ (-1,1),\ (-1,-1)$

Prove that there exists a non-empty subset of vectors whose sum is still $0$.

(In our case: $(0,1) + (1,0) + (-1,-1)=(0,0)$.

-
That was quick. Thanks!! – malenkiy_scot Feb 1 '12 at 14:49
No problem. Yuval Filmus also happens to be a user here; perhaps he will see this question and post an answer! In the meantime, you should make your question title more descriptive. – Rahul Feb 1 '12 at 14:59
Duplicate of mathoverflow.net/questions/7493/… – Eric Naslund Feb 2 '12 at 21:41
@Eric: That's where I'd seen it before! Thanks for pointing it out. Since there is no closing as duplicate of a MathOverflow question, I'll post the link to it as community wiki so the question can be marked as answered. – Rahul Feb 3 '12 at 12:46

• Write each original line as a difference of two $0$/$1$ vectors.
• You now have a function from $\{0,1\}^n$ to $\{0,1\}^n$. Find a cycle.