We have the set of $S=\{1, 2, ..., nm\}$ and we partition it into n subsets of size m in two random ways, which gives us
$ A_1, A_2, ..., A_n$ where $ A_1\cup A_2 \cup ... \cup A_n = S$ and $A_i\cap A_j = \emptyset$ if $i\neq j$.
$ B_1, B_2, ..., B_n$ where $ B_1\cup B_2 \cup ... \cup B_n = S$ and $B_i\cap B_j = \emptyset$ if $i\neq j$.
I want to prove that with changing the indices there's a pairing of $A_i$ and $B_i$s where for each $i$ $A_i \cap B_i \neq \emptyset$
I think Hall's theorem seems to be a good way to go but I don't know how to model the problem into a graph to find a feasible pairing of subsets. Any help?
Hint: Let $G(V,E)$ be a simple bipartite graph with bipartition $V=V_A\sqcup V_B$, where $V_A=\big\{A_1,A_2,\ldots,A_n\big\}$ and $V_B=\big\{B_1,B_2,\ldots,B_n\big\}$, and where two vertices $A_i$ and $B_j$ are joined by an edge if and only if $A_i\cap B_j \neq \emptyset$. Show that $G$ satisfies the marriage condition of Hall's Marriage Theorem.