I have to prove the "simple" König theorem, without using the marriage theorem:
Let $S$ be a set of size $mn$. Suppose that $S$ is partitioned into $m$ subsets, all having size $n$, in two ways: $A_1, A_2, \ldots , A_m$ and $B_1 , B_2 , \ldots , B_m$. Then there exist $m$ distinct elements $a_1 , a_2 , \ldots, a_m$ and a permutation $π$ of $\{1, 2, \ldots, m\}$ such that for all $i$, $a_i \in A_i \cap B_{π(i)}$.
Any hint on how to do it? I can't think of any methodical way of assigning the values of the permutation.