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 nonempty subset of rows that add up to the all zero vector.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Another answer (I guess they must be equivalent):



Hint: starting with the empty set, add vectors one by one and ensure you never get a negative entry in the partial sum. During the process, either you can find a suitable vector (the one which originally had 1's where your current sum has 0's), or you've hit upon a partial sum previously seen  which means the difference is 0. 


One place where it showed up: http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/February2003.html 

