I have been wrestling with an exercise concerning latin squares from the textbook A First Course in Discrete Mathematics by Ian Anderson. The exercise is formulated thus:
A set $S$ of $mn$ elements is partitioned into $m$ sets of size $n$ in two different ways: $S = A_1 \cup ... \cup A_m = B_1 \cup ... \cup B_m$. Show that the sets $B_i$ can be relabelled so that $A_i \cap B_i \neq \emptyset$ for each $i = 1, ..., m$. [Hint: consider the sets $S_i = \{ j : A_i \cap B_j \neq \emptyset\}$.]
I am not sure how to prove this. Here is an example I have completed:
Let $S = \{1,...,25\}, m = 5, n = 5$ and let $$(s_{mn}) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{pmatrix}$$.
Furthermore, let $$A_1 = \{1,6,11,16,21\}, A_2 = \{2,7,12,17,22\}, A_3 = \{3,8,13,18,23\}, A_4 = \{4,9,14,19,24\}, A_5 = \{5,10,15,20,25\}. $$
$$B_1 = \{1,2,3,4,5\}, B_2 = \{6,7,8,9,10\}, B_3 = \{11,12,13,14,15\}, B_4 = \{16,17,18,19,20\}, B_5 = \{21,22,23,24,25\}.$$
Furthermore, $S_1 = S_2 = S_3 = S_4 = S_5 = \{1,2,3,4,5\}$.
I can e.g. relabel the $B_i$s so that $B_1$ becomes $B_2$ etc. and $B_5$ becomes $B_1$ and thus get:
$$(s_{mn}) = \begin{pmatrix} 21 & 22 & 23 & 24 & 25 \\ 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ \end{pmatrix}$$.
Then the condition $A_i \cap B_i \neq \emptyset$ still holds for each $i = 1,...,m$.
I guess I in some kind of way have to use Hall's theorem:
The sets $A_1,...,A_m$ possess an SDR if and only if they satisfy the Hall condition.
Since you suggested Hall's Theorem, let me go ahead with that idea. Define a binary relation of "compatibility" between the sets $A_i$ (the "girls") and the sets $B_j$ (the "boys") by calling $A_i$ and $B_j$ compatible iff their intersection is nonempty. Then the conclusion of Hall's Theorem is exactly the conclusion you want, namely that you can pair up the $A$'s with the $B$'s in such a way that the paired sets intersect. So you need to verify the hypothesis of Hall's Theorem, namely that, for every $k$ girls, there are at least $k$ boys compatible with some of these girls. That is, given $k$ of the $A_i$'s, you want at least $k$ of the $B_j$'s to meet the union of the given $A_i$'s. But that union $U$ has $kn$ elements, and it's covered by the $B_j$'s, no one of which covers more than $n$ elements of $U$. So at least $k$ of the $B$'s must participate in covering $U$.