Linear algebra riddle

Just saw this puzzle from this source. Rephrased in matrix language: elements in a \(n\times(n+1)\) matrix are either \(0\) or \(1\). Every column has at least a \(1\). Show that there are two disjoint column sets such that a row has at least a \(1\) in the first column set if and only if it has at least a \(1\) in the second column set.

==============

Proof:

The matrix has no zero column and its columns are linearly dependent, meaning that we can write

\(a_1v_{i_1}+\ldots+a_nv_{i_n}=b_1v_{j_1}+\ldots+b_mv_{j_m}\)

where \(a_*\) and \(b_*\) are positive, and \(\{v_{i_1},\ldots,v_{i_n}\}\) and \(\{v_{j_1},\ldots,v_{j_m}\}\) are disjoint column sets of the matrix. Since all the numbers involved are non-negative, these two sets satisfy the condition described.