25 海淀二模压轴第三问

· · 学习·文化课

好像被搬到 BNDS 高一年级段考了。

题意：对于任意正整数 n，求证若将 K_n 的边集划分为 m 个满足 1<s<n 的 K_s 的边集无交并（不要求s 都相等），则一定有 m\geq n。

再形式化一下题面，对于一个集族 \{S_1,S_2,\dots,S_m\} 满足 \forall i\in[m],\;1<\lvert S_i\rvert<n\,\land\,S_i\subset[n] 且对于任意 1\leq i<j\leq n 存在唯一的 k\in[m] 满足 i,j\in S_k。

一些入手点是先尝试数学归纳法，发现你需要证明 m=n 时不能存在若干个 S_i 的无交并是 [n]。这提示我们无交并是关键的。接下来施展一些魔法。

证：

把集合 S_i 写成向量 \vec{v_i}，其中 x_j 系数为 [j\in S_i]。

对于 u\in[n]，应有 S_i\setminus\{u\}\,\mid\,i\in[m]\land u\in S_i 是 [n]\setminus\{u\} 的划分，于是有 \sum_{u\in S_i} \vec{v_i}=(\sum_{i=1}^m[u\in S_i]-1)x_u+\sum_{i=1}^nx_i。

记 \vec{t}=\sum_{i=1}^n x_i,\,a_i=\sum_{j=1}^m[i\in S_j]-1。

由于 \forall i\in[m],\;\lvert S_i\rvert<n，因此显然有 \forall i\in[n],\; a_i\geq 1。

前面的和式说明 \vec{t}+a_ix_i\in\operatorname{span}\left(\vec{v_1},\vec{v_2},\dots,\vec{v_m}\right)，接下来只需证明 \operatorname{rank}(\vec{t}+a_1x_1,\vec{t}+a_2x_2, \dots,\vec{t}+a_nx_n)=n。

先做基础行变换将第 i(i>1) 行变成 a_ix_i-a_1x_1，然后再全都代入第一行变成 \left(\sum_{i=1}^n\frac{a_1}{a_i}\right)x_1，由于 a_i 均为正数故系数非 0，然后可以带到后面每一行消成 a_ix_i，因此显然满秩，故 m=\lvert\{\vec{v_1},\vec{v_2},\dots,\vec{v_m}\}\rvert\geq\operatorname{rank}(\vec{v_1},\vec{v_2},\dots,\vec{v_m})\geq\operatorname{rank}(\vec{t}+a_1x_1,\vec{t}+a_2x_2,\dots,\vec{t}+a_nx_n)=n。