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.
 A: 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.
A: The set of subsets of $\{1,2,\ldots,n\}$ is a vector space where addition is defined as the symmetric difference and the scalar field is $\mathbb{Z}_2$.  It's an $n$-dimensional, with basis $\{\{1\},\{2\},\ldots,\{n\}\}$.
Since $\{X_i\}_{i=1}^{n+1}$ is a set of $n+1$ vectors in an $n$-dimensional vector space, it's linearly dependent.  In other words, for some non-empty subset $K \subseteq \{1,2,\ldots,n+1\}$, we have $$\bigoplus_{i \in K} X_i=\emptyset. \tag{*}$$
Pick some $k \in K$.  If $x \in X_k$, but $x \not\in \cup_{i \in K \setminus \{k\}} X_i$, then $x \in \oplus_{i \in K} X_i$, contradicting (*).  Thus $$\bigcup_{i \in K} X_i=\bigcup_{i \in K \setminus \{k\}} X_i.$$
