利用霍尔条件证明匹配的存在性

你这个思路完全找对路子了！用二分图结合霍尔（Hall）定理来证明就是最直接的方案，我帮你把剩下的推导步骤补完整：

首先我们严格定义二分图结构：

• 左顶点集 $U = {A_1, A_2, \dots, A_n}$，对应所有的 $A$ 类集合
• 右顶点集 $V = {B_1, B_2, \dots, B_n}$，对应所有的 $B$ 类集合
• 当且仅当 $A_i \cap B_j \neq \emptyset$ 时，我们在 $A_i$ 和 $B_j$ 之间连一条边

接下来我们只需要验证霍尔条件：对于左顶点集的任意子集 $S \subseteq U$，设 $N(S)$ 是 $S$ 中所有顶点的邻居集合（也就是所有与 $S$ 内 $A_i$ 有非空交集的 $B_j$），必须满足 $|N(S)| \geq |S|$。

推导霍尔条件的过程如下：

1. 设每个 $A_i$ 的基数为 $m$（题目说所有 $A_i$ 不交且等基数），那么任意 $k = |S|$ 个 $A_i$ 的并集大小为 $k \times m$。
2. 这些 $A_i$ 的并集必然包含在 $\bigcup_{B_j \in N(S)} B_j$ 中——因为只有和 $A_i$ 相交的 $B_j$ 才会包含 $A_i$ 里的元素。
3. 再看 $B$ 类集合：题目说所有 $B_j$ 不交且等基数，同时 $\bigcup_{i=1}^n A_i = \bigcup_{j=1}^n B_j$，总元素数为 $n \times m$，所以每个 $B_j$ 的基数也必然是 $m$。
4. 因此 $\bigcup_{B_j \in N(S)} B_j$ 的大小为 $|N(S)| \times m$，结合第二步的包含关系，我们得到不等式：
   $$k \times m \leq |N(S)| \times m$$
5. 两边同时除以正数 $m$，就得到 $k \leq |N(S)|$，也就是 $|S| \leq |N(S)|$，霍尔条件成立。

根据霍尔定理，满足霍尔条件的二分图一定存在完美匹配——也就是存在一个排列 $\pi \in S_n$，使得每个 $A_i$ 都与 $B_{\pi(i)}$ 相连，对应到集合关系就是 $A_i \cap B_{\pi(i)} \neq \emptyset$，这正是我们需要证明的结论。

备注：内容来源于stack exchange，提问作者rubberyhall