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$ 。

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

有大小为 $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$ 的上界，由于作者的精力问题此处不再展开，有兴趣的读者可以查阅参考资料获取进一步的信息。

参考资料

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

与人工智能的交流

Steiner 系统 – 来自 - 数学天地

Steiner 三元系学习小记 - Lynkcat

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

后记

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

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

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

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

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

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