2025 年北京预赛

解答

构造一个二分多重图 $G$。左侧的 $45$ 个顶点表示学生，右侧的 $45$ 个顶点表示号码；学生 $i$ 手中每有一张号码 $j$ 的卡片，就在左顶点 $i$ 与右顶点 $j$ 之间连一条边。重复卡片对应平行边。

每位学生有 $45$ 张卡片，每个号码也恰有 $45$ 张卡片，因此 $G$ 的左右每个顶点度数都为 $45$。任意 $r$ 正则二分多重图都有完美匹配：对左侧任意顶点集 $S$，从 $S$ 发出的 $r|S|$ 条边全部进入邻集 $N(S)$，而 $N(S)$ 至多能承接 $r|N(S)|$ 条边，所以 $|N(S)|\ge |S|$，由 Hall 定理存在完美匹配。

从 $G$ 中依次取出完美匹配。每取出一个，所有顶点度数同时减 $1$，故可一直进行，最终把全部边分解为

这 $45$ 个完美匹配。

把匹配 $F_j$ 中的每张卡片指定给第 $j$ 位学生。由于 $F_j$ 在右侧每个号码顶点恰取一条边，第 $j$ 位学生最终会得到 $1$ 至 $45$ 号卡片各一张。另一方面，每个匹配在左侧每位学生处也恰有一条边，所以对任意两位不同学生 $i,j$：

1. •

   学生 $i$ 手中恰有一张属于匹配 $F_j$ 的卡片，应交给学生 $j$；

2. •

   学生 $j$ 手中恰有一张属于匹配 $F_i$ 的卡片，应交给学生 $i$。

让学生 $i,j$ 直接交换这两张卡片。学生 $i$ 手中属于 $F_i$ 的那张卡片无需移动。对所有无序学生对各进行上述一次交换后，每张需要移动的卡片恰好参加一次交换，每张不需要移动的卡片一次也不参加；而第 $j$ 位学生恰好收齐匹配 $F_j$ 的全部 $45$ 张卡片。因此所求交换方案存在。