= Solution
Make a <bipartite graph> whose two classes index the two partitions, joining $i$ on the left to $j$ on the right exactly when $A_i\cap B_j\ne\varnothing$. For a subset $U$ of left indices, its <union> of blocks contains $2008|U|$ elements. They all lie in the blocks indexed by $N(U)$, whose <union> has $2008|N(U)|$ elements. Thus $|N(U)|\ge|U|$. Hall's theorem gives a <matching> covering all $n$ left vertices, hence also all $n$ right vertices. Its partner map is the required permutation $\pi$.
Back to article page
