当前位置：首页 > news >正文

Steiner 系初探

news 2026/5/12 1:43:59

我好久没有写学术文章了，因为对比起大家在研究的内容，文化课上的内容实在是缺乏美感与研究价值。

废话少叙，让我们来看一些有意思的东西。

引入：沪卷一模 12 题。

设平行四边形 \(A_1A_2A_3A_4\)，定义集合\(\Omega = \left\{ \overrightarrow{A_iA_j} \mid i \neq j, i,j \in \{1,2,3,4\} \right\}\)（\(\Omega\) 中的元素为不同的向量，相等的向量视为同一个元素）。

现从集合 \(\Omega\) 中选取若干个四元子集，满足：任意两个不同的四元子集 \(M_m, M_n\)，其交集的元素个数满足 \(|M_m \cap M_n| \leq 2\)。

求满足上述条件的四元子集的最大个数 \(x\)。

问题形式有两种等价表述：

有大小为 \(n\) 的全集 \(\Omega\)，现选出 \(x\) 个大小为 \(m\) 的子集 \(A_1,\cdots,A_x\)，使得它们两两交的大小不超过 \(k\)，最大化 \(x\)。
有大小为 \(n\) 的全集 \(\Omega\)，现选出 \(x\) 个大小为 \(m\) 的子集 \(A_1,\cdots,A_x\)，使得每个大小为 \(k+1\) 的子集至多出现在 \(1\) 个被选中的子集中，最大化 \(x\)。

在文化课（以及强基）中，上述两种表述的等价性是第一个考察重点，其中第二种表述是更有用的，因为它给出了 \(x\) 的一个上界：

\[x\binom{m}{k+1}\le \binom{n}{k+1} \]

即鸽巢原理：一共有 \(\binom{n}{k+1}\) 个不可共有的子集，每个大小为 \(m\) 的集合会占有 \(\binom{m}{k+1}\) 个。

当 \(x\) 顶到上界时，这个结构叫做 Steiner 系，与广为流传的斯坦纳树的提出者是同一个人，\(x\) 能否顶到上界是一个 open 的问题，但通常只会考察能顶到上界的情况，并且会出得易于构造。

值得注意的是本题特有的一种构造方法：仿射空间。

以原题为例，易得 \(n=8\)（注意重复的向量），\(m=4,k=2\)，进一步我们能求出 \(x\le 14\)，如何构造这个上界呢？

考虑一个大小为 \(n=2^3\) 的线性空间（\(3\) 维，边长为 \(2\) 的立方体），我们可以将 \(m=4\) 视为一个由 \(1\) 个限制确定的 \(2\) 维线性子空间的大小，将 \(k=2\) 视为两个上述线性子空间的交的大小，这样我们会发现两个大小为 \(m\) 的线性子空间的交确实至多是 \(k\)。

于是我们发现限制是可以天然满足的。

平面的个数我们考虑先统计包含 \((0,0,0)\) 的面再计算它的平行面（也称陪集/仿射子空间）。

包含 \((0,0,0)\) 的面我们考虑用两个向量去张出来（其实就是由 \(2\) 个基向量张成的二维线性子空间，该子空间包含 \(2²=4\) 个点），考虑每个面中有 \(3\) 个非零向量，它们两两异或得到另一个，所以平面的个数是 \(\binom{2^3-1}{2}\div3=7\)，算上平行面再乘上 \(2\)，得到答案为 \(14\)。

注：我本以为这个方法是十分普适的，但是推广了一下发现十分困难。

不过很好的一点是，对于 \(k=1,n=m^u\) 的情况下，这可以是一种好的构造方法，此时相当于找到所有方向的线并算上平行线，这个东西是可以计数的，我们可以借助高斯二项式系数来验证该构造能够取到 \(x\) 的上界，由于作者的经历问题此处不再展开，有兴趣的读者可以查阅参考资料获取进一步的信息。