2022 年中科大少年班复试 · 第 5 题

解答

若有两个矩形交集为空，把它们与任一第三个矩形放在交集一侧，交集就是空集，结论立即成立。以下只考虑任意两个矩形都相交的情形。

写每个矩形为

分别选取左界最大的、右界最小的、下界最大的、上界最小的矩形。四次选择至多涉及四个不同指标，所以存在一个没有被选中的指标 $e$。记 $E=A_e$，其余四个指标组成集合 $I$。

在 $I$ 中定义四个非空的指标集

它们非空，因为每个方向预先选出的最强约束都来自 $I$。

若存在 $j\in I$，使四个集合中没有一个恰为 $\{j\}$，则删去 $j$ 后每个集合仍非空。对任意属于其余三个矩形交集的点，每种坐标边界都至少被一个留下的矩形约束得不弱于 $E$，因此

于是选 $E,A_j$ 作为并集一侧，即已满足要求。

若不存在这样的 $j$，则 $I$ 的每个指标都必须是某个 $C$ 的唯一元素。共有四个指标和四个非空集合，故这四个集合必为四个不同的单元集合。设

由于 $p$ 不属于其余三个集合，$A_p$ 在右界和上下边界上都严格包含 $E$ 的相应范围；因此一个 $E$ 中的点只要满足 $x\ge {\ell }_p$，就属于 $A_p$。同理，一个 $E$ 中的点只要满足 $x\le r_q$，就属于 $A_q$。

又因 $A_p,A_q$ 相交，有 ${\ell }_p\le r_q$。所以每个实数 $x$ 都满足 $x\ge {\ell }_p$ 或 $x\le r_q$，从而

剩下的三个矩形包括 $E$，它们的交集也就包含于 $A_p\cup A_q$。

两类情形都找到了所需的两个矩形。记其余三个矩形的交集为 $K$，便有