Steiner 系初探

· · 算法·理论

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

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

引入：沪卷一模 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。

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

在文化课（以及强基）中，上述两种表述的等价性是第一个考察重点，其中第二种表述是更有用的，因为它给出了 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 的上界，由于作者的经历问题此处不再展开，有兴趣的读者可以查阅参考资料获取进一步的信息。

参考资料

退役 oier 交流群于 2026/2/18 下午的聊天记录

与人工智能的交流

Steiner 系统 -- 来自 - 数学天地

Steiner 三元系学习小记 - Lynkcat

高斯二项式系数 - 百度百科

后记

我不便于在一篇学术文章中倾注太多感情，不过还是有一些感想。

文化课如同一场巨大的风暴，抛开浸在其中的种种极端作息来看，它还将我在算法竞赛中养成的一些研究问题的能力消磨得极为生疏，敲下这些文字时，曾经无数个面对屏幕冥思苦想的日日夜夜浮现在眼前，随之一起的是个中的激情、友谊与狂热。

我对曾经的时光越发思念，可我也时常担心太多的执念会模糊它本来的样子，我所热爱的，远非一个只存于理想中的社区，而是真实存在的，帮助过我的，并一直牵着我的社区，所以我执意将偶然遇到的这个小知识点探索下去，总结起来，让我找到些旧日的情感。

我对自己的笔记持有一些完美主义的执念，总是希望将它打磨的无比易于阅读，希望能对这个社区起到一些贡献，哪怕多出的打磨时间对我本人没什么附加作用，我还是觉得，既然要发表在这个社区中，就应该与我知识的来源秉持相同的精神，是社区中无数的文章给了我这份知识，我自当以相同的价值回馈于它。

无言，希望这篇笔记能帮到大家。

（本文写到一半写嗨了感觉特别完美，结果扔给 AI 一看核心结论爆炸了，只好草草收场，令人唏嘘。）