# 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)$.

• cs.toronto.edu/~yuvalf/pm1%20Vectors%20Riddle.pdf
– user856
Feb 1 '12 at 14:39
• That was quick. Thanks!! 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.
– user856
Feb 1 '12 at 14:59
• Duplicate of mathoverflow.net/questions/7493/… 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.
– user856
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.