Let $n >0$ and $(X_i)_{i \in [\![ 1,n+1 ]\!]}$ be non empty subsets of $[\![ 1,n ]\!]$. Show that there exists two disjoints non empty subsets $I$ and $J$ of $[\![ 1,n+1 ]\!]$ such that $$\bigcup_{i\in I}X_i = \bigcup_{j\in J}X_j $$
I found a solution using Hall theorem but I forgot it. Can someone help me ?
I don't need solution using linear algebra. I don't. If someone could provide me some solution using combinatorics...
Consider a bipartite graph with the $X_i$'s on one side and $1,\ldots,n$ on the other side. If $X_i$ contains $k$, then $X_i$ is connected with $k$. So the above theorem is now equivalent to:
For a bipartite graph $H$ with bipartitions $X$ and $Y$ such that $|X| = n+1$ and $|Y| = n$ and degree of every vertex of $X$ is greater than $0$, there exists two disjoint subsets of $X$ with the same neighbourhood set in $Y$.
Let us induct on $n$.
Base case: $n = 1$
For $n=1$, both the vertices in $X$ is connected to the single vertices in $Y$. So both $\{X_1\}$ and $\{X_2\}$ have the same neighbourhood. Hence proved
Definitions:
A vertex $v$ is said to be saturated by a matching $M$ if $v$ has an edge incident on it in $M$.
Hall's theorem:
Let $G$ be a bipartite graph with bipartition $(X,Y)$ , then $G$ contains a matching that saturates every vertex in $X$ if and only if $|N(S)| \geq |S|$ for all $S \subseteq X$ (where $N(S)$ is the neighbourhood of $S$).
Inductive case: Let us assume the above theorem is true for all integers less than $n$ and let us try to prove for $n$.
Case 1: $H$ does not have any matching that saturates every vertex in $Y$.
Since $H$ does not contain any matching that saturates $Y$, by Hall's theorem, there exists an $S$ such that $S$ is a subset of $Y$ and $|N(S)| < |S|$ . Now consider the graph $H'$ with bipartitions $X \setminus N(S)$ and $Y \setminus S$. Since $|X \setminus N(S)| > |Y \setminus S|$, by induction, $H'$ has two vertex sets that satisfy theorem. We can clearly see that those two vertex sets also satisfy the theorem in $H$ (Because those two vertex sets won't get any extra edges after we add back $N(S)$ and $S$). Hence proved.
Case 2: $H$ has a matching $M$ that saturates every vertex in $Y$.
$M$ must saturates $n$ vertices in $X$. Let the unsaturated vertex in $X$ be $u$. Consider the maximum $M$-alternating tree rooted at $u$. All the odd levels in this tree will have vertices from $Y$ and all even levels in the tree will have vertices from $X$.
All the leaves of this tree will be vertices from $X$. Let us prove this by contradiction. Let $v$ be a vertex in $Y$ that is a leaf in the $M$-alternating tree. Every vertex in $Y$ is reached by a edge not in $M$. Since $Y$ is saturated by $M$, $v$ has an edge $e \in M$. We can now take $e$ and reach another vertex $w$ and extend the maximum $M$-alternating tree by adding $e$. Hence contradiction. Hence $v$ is not a leaf. Hence proved.
Consider the sets of all vertices in $4k$ and $4k+2$ levels for $k \in \mathbb(W)$. $u$ belongs to $0$th level. Both these sets have the same neighbourhood. Let us prove this by contradiction. Let us assume they don't have the same neighbourhood in $H$. Let a vertex $w$ in one of $4k$ level vertices be connected to a vertex $v$ which is not connected with any $4k+2$ level vertex. Then $v$ is a leaf in the $M$-alternating tree. But we proved that all leaves of $M$-alternating tree are in $X$. But $v \in Y$. Hence contradiction. Similarly we can prove that for vertex $u$ in $4k+2$ level connected to a vertex $v$ not connected with a $4k$ level vertex leads to contradiction. So both vertex sets have the same neighbourhood.