Finding Distinct Elements and Permutation in Partitioned Set

Question

I am having a hard time figuring out where to start on a homework problem.

The question is:

A set of $nk$ elements is partitioned into $k$ subsets in two ways, each subset having size $n$: one is $A_{1},...,A_{k}$, and another is $B_{1},...,B_{k}$. Show that there exist distinct elements $x_{1},...,x_{k}$ and a permutation $\pi$ of $\{1,...,k\}$ such that $x_{i}\in A_{i}\cap B_{\pi(i)}$ for $1 \leq i \leq k$.

I understand how the set is partitioned, but when it comes to showing the distinct elements I am lost. I've read the lecture notes a few times over and I can't figure out how they relate to this question. The notes cover Mantel's Theorem, Menger's Theorem, Galli Identities, and Hall's Theorem. Can anyone show me how I can use any of those theorems to work the problem?

Thanks in advance.

Answer 1

Choose $x_{1}\in A_{1}$ arbitrarily, and choose $\pi(1)$ such that $x_{1}\in B_{\pi(1)}$.

Since $x_{1}\in B_{\pi(1)}$ and $x_{1}\notin A_{2}$, there exists $x_{2}\in A_{2}$ such that $x_{2}\notin B_{\pi(1)}$.

Now choose $\pi(2)$ such that $x_{2}\in B_{\pi(2)}$.

Since $x_{2}\in B_{\pi(2)}$ but $x_{2}\notin A_{3}$....

Edit:

My answer is incorrect. The process works only if $n = 2$.

If $n\geq 3$, there is not reason not to expect $A_{3}\subset B_{\pi(1)}\cup B_{\pi(2)}$. At this point you'd have to go back and "repair" the choice of $x_{1},x_{2}$. The complexity would explode as you get further along. I expect there is some machinery that you'd need to use which has already dealt with this.

Answer 2

I think that Halls theorem helps here. You have two sets of partitions..you can add a link between $A_i$ and $B_j$ iff $A_i \cap B_j \neq \emptyset$ and that makes a bipartite graph (G=(V,E)). So the Marriage theorem (Corollary of Halls theorem) says that you would have a perfect matching iff you have that $|X|\leq |\phi (X)|$ for every $X\subset \{A_1,\ldots ,A_k\}$ where $\phi (X)=\{Y: \{X,Y\}\in E(G)\}$. So you must prove that for every subset X of the sequence $\{A_1,\ldots A_k\}$ , $|X|\leq |\phi (X)|$. I think it can be done by contradiction.