柯西不等式与组合计数估计

一句话

组合计数题里常常数出这样的式子：某些量 $d_{1}, \dots, d_{n}$ 的“两两配对数”被控制住了，即 $\sum C_{d_{i}}^{2} \leq K$ 。可我们想估计的却是总数 $D = \sum d_{i}$ 。中间差的那一步，正是柯西不等式：

\sum d_{i}^{2} \geq \frac{( \sum d _{i} ) ^{2}}{n} = \frac{D ^{2}}{n} .

于是 $\frac{D ^{2}}{n} - D \leq \sum d_{i}^{2} - \sum d_{i} = 2 \sum C_{d_{i}}^{2} \leq 2 K$ ，解这个关于 $D$ 的二次不等式就得到上界。算两次给出平方和的上界，柯西把它变成总数的上界。 等号要求所有 $d_{i}$ 相等——这也告诉我们最好的构造长什么样。

7 × 7 的方格最多填几格而没有矩形

第 1 / 5 步

矩形 = 两行共用两列
四个角都填了的矩形，就是某两行在同样的两列上都有格子。所以“无矩形”等价于：任何一对列，至多被一行同时占用。

$无矩形 ⟺ 每个列对至多被一行用到$
算两次：数“行里的列对”
柯西：从平方和到总数
解出上界
真的有：法诺平面

先猜后证

$5 \times 5$ 的方格，无矩形，最多能填几格？（先用上面的方法算上界，再到页首去摆。）

格

先选定答案，才能看到结论。

第 1 站 · 图论：没有四边形的图

$n$ 个点的简单图，其中没有长为 $4$ 的圈。最多有几条边？

把“方格的行”换成“顶点”：顶点 $v$ 的度数是 $d_{v}$ ，它的邻居两两配对，得到 $C_{d_{v}}^{2}$ 个“以 $v$ 为中点的折线”。没有四边形，等价于任意两点至多有一个公共邻居，所以

v \sum C_{d_{v}}^{2} \leq C_{n}^{2}, v \sum d_{v} = 2 e .

柯西： $\sum d_{v}^{2} \geq \frac{4 e ^{2}}{n}$ ，于是 $\frac{4 e ^{2}}{n} - 2 e \leq n (n - 1)$ ，解得

e \leq \frac{n}{4} (1 + 4 n - 3) .

$n = 5$ 时右边约 $6.4$ ，所以 $e \leq 6$ ；两个共用一个顶点的三角形（“蝴蝶结”）正好 $6$ 条边、没有四边形。

第 2 站 · 集合族：两两至多一个公共元

$9$ 个人组成若干个 $4$ 人委员会，任何两个委员会至多有一个公共成员。最多能有几个委员会？

这次让人当“行”：第 $p$ 个人参加了 $d_{p}$ 个委员会。他所在的委员会两两配对，配出的委员会对互不重复（否则两个委员会有两个公共成员），所以

p = 1 \sum 9 C_{d_{p}}^{2} \leq C_{m}^{2}, p \sum d_{p} = 4 m .

柯西： $\sum d_{p}^{2} \geq \frac{16 m ^{2}}{9}$ ，代入得 $\frac{16 m ^{2}}{9} - 4 m \leq m (m - 1)$ ，即 $7 m \leq 27$ ， $m \leq 3$ 。构造： ${1, 2, 3, 4}$ 、 ${4, 5, 6, 7}$ 、 ${7, 8, 9, 1}$ 。

三站的骨架完全一样：找出“配对数”的上界（算两次）→ 柯西把平方和换成总数 → 解二次不等式 → 构造验证。

练一练

练习 1基础

$4 \times 4$ 的方格中填若干格，使任何矩形的四个角不全被填。最多能填几格？

练习 2基础

$6$ 个人组成若干个 $3$ 人小组，任何两个小组至多有一个公共成员。最多能有几个小组？

练习 3提高

$5$ 个顶点的简单图中没有长为 $4$ 的圈。最多有几条边？

练习 4挑战

$6 \times 6$ 的方格中，任何矩形的四个角不全被填。最多能填几格？

一句话

7 × 7 的方格最多填几格而没有矩形

第 1 站 · 图论：没有四边形的图

第 2 站 · 集合族：两两至多一个公共元

练一练

错误博物馆 · 本站展品

把“平均每行”当成“每一行”