2025 高考数学（北京）压轴题另解
Apteryxx
·
·
学习·文化课
思路来自柳宏谦。
设顶点集 V = \{\langle x, y \rangle : x \in \{1, 2, \dots, 8\} \land y \in \{1, 2, \dots, 8\}\}，边集 E = \{ \{ \langle x_0, y_0 \rangle, \langle x_1, y_1 \rangle \} : (|x_0 - x_1| = 3 \land |x_0 - x_1| = 4) \lor (|x_0 - x_1| = 4 \land |x_0 - x_1| = 3)\}，图 G = (V, E)。易证原问题等价于证明 G 不存在 Hamilton 路径。
> **引理**
>
> 偶数个顶点的二分图 $G$ 存在完美匹配是 $G$ 存在 Hamilton 路径的必要条件。
>
> **证明**
>
> 设 $G$ 的一条 Hamilton 路径为 $p_1, p_2, \dots, p_{2n}$。易证 $\{\{p_1, p_2 \}, \{p_3, p_4\}, \dots, \{p_{2n - 1}, p_{2n}\}\}$ 是 $G$ 的完美匹配。
取 $S = \{\langle 1, 2 \rangle, \langle 1, 6 \rangle, \langle 1, 8 \rangle, \langle 2, 1 \rangle, \langle 2, 7 \rangle, \langle 6, 1 \rangle, \langle 6, 7 \rangle, \langle 7, 2 \rangle, \langle 7, 6 \rangle, \langle 7, 8 \rangle\}$，则 $N_G(S) = \{\langle 2, 4 \rangle, \langle 3, 3 \rangle, \langle 3, 5 \rangle, \langle 4, 2 \rangle, \langle 4, 4 \rangle, \langle 4, 6 \rangle, \langle 5, 3 \rangle, \langle 5, 5 \rangle, \langle 6, 4 \rangle\}$。$|S| > |N_G(S)|$，由 Hall 定理有 $G$ 不存在完美匹配。由引理有 $G$ 不存在 Hamilton 路径。
