Given a set of vectors $V$ in $Z_2^n$, such that each coordinate(i.e. from $1$ to $n$) is one in at least one of them, prove that there is a linear combination of these vectors that has $1$ for at least half of it's coordinates.
This is how I've approached the problem so far: Define matrix $A$ with the vectors of $V$ as it rows. Let $R$ be the echelon-row-reduced matrix of $A$, obviously the rows of $R$ and $A$ span the same space. And given the fact that each coordinate was originally non-zero in at least one of the vectors, we can conclude it is non-zero in at least one of the rows of $R$. Let's call the columns which start a row in $R$ special. If there are at least $\frac{n}{2}$ special columns, then the problem is solved(we combine all rows). Otherwise we have more than $\frac{n}{2}$ special columns distributed in less than $\frac{n}{2}$ rows. But I don't know where to go from here.
I also have an extra question, given $V$ is there way to determine what is the maximum number of non-zero coordinates a linear combination of it's vectors can have?