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.
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 subset of rows that add up to the all zero vector.