分类讨论与极端原理

在有限多个(点,过两点的直线)且该点不在该直线上的组合中,选出距离严格最小的一组;若这条最近的直线上还有第三个点,几何论证会构造出一组更近的组合,这与最小性矛盾。

第一步(设置极端选择)。 设 $P$ 为给定的有限点集,共有 $n \ge 3$ 个点且并非全部共线。考虑由所有满足下述条件的组 $(Q, \ell)$ 组成的有限集合:$\ell$ 是过 $P$ 中至少 $2$ 个点的直线,且 $Q \in P$ 是不在 $\ell$ 上的点。由于 $P$ 并非全部共线,该集合非空,又因其有限,由极端原理可以选出使点到直线的距离 $d(Q_0, \ell_0)$ 最小的一组 $(Q_0, \ell_0)$。

第二步(假设矛盾)。 为得出矛盾,假设 $\ell_0$ 上至少有 $3$ 个 $P$ 中的点。设 $F$ 为从 $Q_0$ 向 $\ell_0$ 所作垂线的垂足。由于 $\ell_0$ 上有 $\ge 3$ 个 $P$ 中的点,而它们只能位于沿 $\ell_0$ 从 $F$ 出发的至多 $2$ 条射线上,由鸽笼原理可知其中有两点 $B$ 与 $C$ 位于同一条射线上,且 $B$ 位于 $F$ 与 $C$ 之间(允许 $B = F$)。

第三步(通过相似三角形构造更近的一组)。 从 $B$ 向直线 $Q_0C$ 作垂线,垂足为 $G$。直角三角形 $\triangle BGC$ 与 $\triangle Q_0FC$ 在 $C$ 处共享同一角,因而相似,由此得到 $\dfrac{BG}{Q_0F} = \dfrac{BC}{Q_0C}$。由于 $B$ 位于 $F$ 与 $C$ 之间,有 $BC \le FC$;又因 $\triangle Q_0FC$ 在 $F$ 处为直角,其斜边满足 $FC < Q_0C$;综合两者得 $BC < Q_0C$,从而 $BG < Q_0F = d(Q_0, \ell_0)$。

第四步(矛盾)。 直线 $Q_0C$ 经过 $P$ 中的 $2$ 个点(即 $Q_0$ 与 $C$),而 $B$ 是不在其上的 $P$ 中的点,因此 $(B, Q_0C)$ 是我们有限集合中的一组合法组合,且满足 $d(B, Q_0C) = BG < d(Q_0, \ell_0)$,这与 $(Q_0, \ell_0)$ 的最小性矛盾。

第五步(结论)。 该矛盾表明 $\ell_0$ 不可能包含 $3$ 个或更多 $P$ 中的点;既然它被选定为至少包含 $2$ 个点,那么它恰好包含 $2$ 个点,故 $\ell_0$ 即为所求的寻常直线。

取一条长度最大的有向路径;若存在某个被遗漏的顶点,锦标赛的性质(每一对都存在一条有向边)就能让我们在某一端延长该路径,或把缺失的顶点插入中间,这与最大性矛盾。

第一步(极端选择)。 在锦标赛的所有有向路径中,选出顶点数 $k$ 最大的一条 $P: v_1 \to v_2 \to \cdots \to v_k$;由于顶点只有有限多个,这个最大值必定存在。为得出矛盾,假设 $k < n$,并设 $u$ 为不在 $P$ 上的一个顶点。

第二步(在两端分类讨论)。 由于锦标赛中 $u \to v_1$ 与 $v_1 \to u$ 恰有一个成立:若 $u \to v_1$ 成立,把 $u$ 加到最前面就得到更长的路径 $u \to v_1 \to \cdots \to v_k$,与 $k$ 的最大性矛盾;因此 $v_1 \to u$ 成立。同理,$v_k \to u$ 与 $u \to v_k$ 恰有一个成立:若 $v_k \to u$ 成立,把 $u$ 加到最后面就得到更长的路径,与最大性矛盾;因此 $u \to v_k$ 成立。

第三步(确定插入位置)。 现在已知 $v_1 \to u$ 与 $u \to v_k$。设 $j$ 为 $\{1, \dots, k-1\}$ 中使 $v_j \to u$ 成立的最大下标;由于 $j = 1$ 满足条件,该下标集合非空,故由极端原理 $j$ 存在。由 $j$ 的最大性,弧 $v_{j+1} \to u$ 不成立,于是锦标赛的性质迫使 $u \to v_{j+1}$ 成立。

第四步(通过插入得到矛盾)。 结合 $v_j \to u$ 与 $u \to v_{j+1}$,把 $u$ 插入 $v_j$ 与 $v_{j+1}$ 之间,得到路径 $v_1 \to \cdots \to v_j \to u \to v_{j+1} \to \cdots \to v_k$,它有 $k + 1$ 个顶点,与 $k$ 的最大性矛盾。

第五步(结论)。 这样的顶点 $u$ 不可能存在,故 $k = n$,$P$ 即为一条哈密顿路径。