2026 年广东预赛

提示

先独立尝试，再展开工具说明与想法来源。

思路

这里使用极值图论的 Turán 定理：不含 $r + 1$ 点完全子图的 $N$ 点图，边数不超过平衡完全 $r$ 部图。部内不连、部间全连；部越均匀，扣掉的组内配对越少。此处取 $r = 7$ ，胜负模板的合法性还须另外逐点检查；该定理本身不是普通高中课内结论。

想法从哪来：先把“赛过”和“胜负”拆开，分别用边和箭头表示。三人各胜一次正好形成有向三角形；没有这种三角形的完全比赛可按胜负排成一条传递次序。为限制总场数，先问多大的全互赛小组一定出现禁止的传递四人组。固定一人，至少四个同向邻点即可推出八人全互赛不可能。上界于是转成无 $K_{8}$ 图的边数问题。构造也反过来做：先找七人胜负模板，让每人的三个出邻点恰成三角形，再把每个点放大为人数尽量均衡的一组。模七的 $1, 2, 4$ 差集用于实现这个局部条件，而非凭空猜一百人的赛程。

把已比赛的两人连边，并把边从胜者指向负者。三人每人恰胜一场就是一个有向三角形；题设等价于每个四点完全子图的定向都不是传递的。任意八点竞赛图必含传递四点组，因此底层图必须不含 $K_{8}$ ，上界由 Turán 定理给出。等号构造需要一张不含传递 $K_{4}$ 的七点竞赛图，再做平衡放大。

解答

建立有向图：两名选手比赛过就连边，方向由胜者指向负者。一个四点完全子图若没有三人循环胜负，则其竞赛图是传递的。因此题设要求每个 $K_{4}$ 的定向都不是传递竞赛图。

先证明底层无向图不含 $K_{8}$ 。任意八点竞赛图中，取一个顶点 $v$ ，其出邻点或入邻点至少有四个。任意四点竞赛图都含传递三点组：取其中出度至少为 $2$ 的一点，它与它所胜的两点即组成传递三点组。于是，在 $v$ 的同向邻点中可取传递三点组；再加入 $v$ ，便得到传递四点组。这与题设矛盾，故底层图是 $K_{8}$ -自由图。

由 Turán 定理， $100$ 个顶点的 $K_{8}$ -自由图边数至多由平衡完全七部图达到。这里

100 = 2 \cdot 15 + 5 \cdot 14,

故比赛场数至多为

(2 100) - 2 (2 15) - 5 (2 14) = 4950 - 210 - 455 = 4285. (1)

为使上界论证自足，可用标准对称化证明上述 Turán 结论：在极大边数的无 $K_{8}$ 图中，不相邻且邻集不同的两点可把较小度者替换为较大度者的同邻点而不减边数且不产生 $K_{8}$ ；反复进行后得到至多七部的完全多部图，而各部大小相差至多一时边数最大。

下面构造达到 (1) 的赛程与胜负。把选手分为七组，其中两组各 $15$ 人、五组各 $14$ 人；同组之间不比赛，不同组之间全部比赛。用模 $7$ 的数 $0, 1, \dots, 6$ 标记各组，并规定当

j - i (mod 7) \in {1, 2, 4}

时，第 $i$ 组所有选手战胜第 $j$ 组所有选手。

这个七点竞赛图不含传递四点组。事实上，每个顶点 $i$ 恰有三个出邻点 $i + 1, i + 2, i + 4$ ，而这三点依次构成有向三角形

i + 1 ⟶ i + 2 ⟶ i + 4 ⟶ i + 1.

若存在传递四点组，其源点必须战胜另外三点，于是另外三点正好是该源点的全部出邻点，但它们并不传递，矛盾。

任意四名两两比赛过的选手来自四个不同组，它们在七点竞赛图中不是传递四点组，因而含有一个有向三角形。对应的三名选手每人恰胜一场，满足题设。因此最大比赛场数为

4285 .

复核

“四人中存在三人每人一胜”与“该四点竞赛图含有向三角形”等价；竞赛图无有向三角形当且仅当它是传递的。构造中同组无边，所以任何四名两两比赛者确实必须来自四个不同组。

方法总结

带胜负关系的赛程极值题可拆成两层：先用有向图局部条件推出底层无向图禁含某个完全图，再用极值图论求边数；等号构造则用一个小型定向模板做完全多部图的放大。

作答

解析

提示

思路

解答

复核

方法总结