# A riddle about zeros, ones and minus-ones

I was asked this years ago, but I don't remember by whom, and have never managed to solve it. Consider the $2^n \times n$ matrix of all vectors in {-1,1}$^n$. Someone comes and maliciously replaces some of the entries by zeros. Show that there still remains a non-empty subset of rows that add up to the all zero vector.

-
To see if I understand your situation properly, you're taking 2^n vectors of n elements such that each element in the matrix is a -1 or a 1, and no two vectors are the same? I would think that a proof for such would use induction, but I'm not sure how it would work. –  Gabriel Benamy Dec 1 '09 at 20:36
How about the smpty subset? ;-) –  Kevin Buzzard Dec 1 '09 at 20:47
@buzzard: I took the liberty of inserting the non-empty word. –  Ilya Nikokoshev Dec 1 '09 at 21:06
I hope for your sake the problem is correct with that modification :-) –  Kevin Buzzard Dec 1 '09 at 21:21
"Someone comes and maliciously replaces some of the words by other words. Show that the problem still has a solution" –  Kevin Buzzard Dec 1 '09 at 21:22
show 1 more comment

Another answer (I guess they must be equivalent):

• Write each original line as a difference of two 0/1 vectors.
• Adapt this representation to the modified lines by changing only the subtrahends.
• You now have a function from {0,1}^n to {0,1}^n. Find a cycle.
-
For the archive: The function in step 3 is the one that maps each minuend to the corresponding changed subtrahend. -- Great solution! –  darij grinberg Jul 18 '10 at 23:48