Given $n+1$ subsets of $\{1,2,...,n\}$, we can find two families of subsets with the same union Let $F=\{X_1,..X_{n+1}\}$ be a family of nonempty subsets of $\{1,2,...,n\}$. Show that there exist two disjoints subsets $I$ and $J$ of $\{1,2,...,n+1\}$ such that 
$\bigcup_{i \in I} X_i=\bigcup_{j \in J} X_j$

Apparently there is a solution using linear algebra but I don't see how.

Associate $X_i$ with the vector $\mathbf{v}_i$ of length $n$ which has a $1$ in coordinate $r$ if $r\in X_i$, and $0$ otherwise. All the $\mathbf{v}_i$ are in $\mathbb R^n$, which has dimension $n$, but there are $n+1$ of them so they are linearly dependent, i.e. there is some expression $\sum a_i\mathbf{v}_i=\mathbf{0}$, where the $a_i$ are not all zero. Write $I=\{i:a_i>0\}$ and $J=\{i:a_i<0\}$. Then $$\sum_{i\in I} a_i\mathbf{v}_i=\sum_{i\in J} -a_i\mathbf{v}_i.$$
Now the LHS has a positive coordinate anywhere in the union corresponding to $I$, and is $0$ everywhere else, and the RHS corresponds to $J$ in the same way, so the unions are equal. $a_i$ are not all zero, so at least one of $I,J$ is nonempty, but none of the $X_i$ is empty so they must both be nonempty.
