竞赛数学与解题

奥林匹克不等式

竞赛数学中证明不等式的核心工具箱:AM–GM–HM $\frac{a_1+\dots+a_n}{n} \ge \sqrt[n]{a_1\cdots a_n}$ 、柯西–施瓦茨 $\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2$ 及其伙伴 Titu 引理 $\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}$ 、排序不等式、切比雪夫不等式、詹森不等式,以及舒尔不等式 $a^r(a-b)(a-c) + b^r(b-a)(b-c) + c^r(c-a)(c-b) \ge 0$ 。我们通过 $\sum(a_i t - b_i)^2 \ge 0$ 的判别式给出柯西–施瓦茨的完整证明,并证明 $r=1$ 时的舒尔不等式,然后将这些工具应用于信噪比界限和 Kullback–Leibler 散度。

直观为什么平均值会如此表现

取两个正数,比如 $4$ 和 $9$ 。它们的算术平均是 $\frac{4+9}{2}=6.5$ ,但几何平均是 $\sqrt{4\cdot 9}=6$ 。几何平均总是更小(当两数相等时相等)——把两个不相等的数挤在一起相乘,比把它们相加"损失"更多。将这一简单观察推广到 $n$ 个数,并与几个伙伴不等式(柯西–施瓦茨、排序不等式、切比雪夫、詹森、舒尔)结合,便是竞赛数学家用来证明一个代数式总是不小于另一个式子的全部工具箱——把看似要搜索无穷多种情形的问题,变成几行简洁的代数。

将

4,9

的算术平均

6.5

与几何平均

6

之间的差距描绘为曲线:调整参数看

f(x) = -x^2+13

如何可视化 AM–GM 差距

\left(\frac{a+b}{2}\right)^2 - ab = \left(\frac{a-b}{2}\right)^2 \ge 0

。

中学AM–GM–HM 与柯西–施瓦茨

定义: 三种平均值比较

对正实数 $a_1,\dots,a_n$ ,算术平均为 $\frac{a_1+\dots+a_n}{n}$ ,几何平均为 $\sqrt[n]{a_1\cdots a_n}$ ,调和平均为 $\frac{n}{\frac{1}{a_1}+\dots+\frac{1}{a_n}}$ 。AM–GM–HM 链断言算术平均 $\ge$ 几何平均 $\ge$ 调和平均,当且仅当 $a_1=\dots=a_n$ 时处处等号成立。

\frac{a_1+\dots+a_n}{n} \ge \sqrt[n]{a_1\cdots a_n} \ge \frac{n}{\frac{1}{a_1}+\dots+\frac{1}{a_n}}

柯西–施瓦茨将这个想法锐化为点积形式: $\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2$ 。一个直接推论,Titu 引理(Engel 形式),对竞赛中的分式往往更方便: $\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}$ ,通过将 $a_i \to a_i/\sqrt{b_i}$ 和 $b_i \to \sqrt{b_i}$ 代入柯西–施瓦茨得到。

\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}

选用哪个不等式
工具	最适用场景
AM–GM	积与和的比较,定和优化
柯西–施瓦茨 / Titu	分式之和,点积界限
排序 / 切比雪夫	有序数列乘积之和
詹森	均值的凸/凹函数
舒尔	对称三元不等式

大学完整证明:柯西–施瓦茨与舒尔

定理: 柯西–施瓦茨不等式

对实数 $a_1,\dots,a_n$ 与 $b_1,\dots,b_n$ : $\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2$ ,等号成立当且仅当两数列成比例。

为什么成立?

这个不等式(以及其 Engel 形式的推论 Titu 引理)是奥数不等式问题中最有用的单一工具,能将分式或乘积之和转化为易于处理的界。

证明

第1步:构造辅助二次式。 考虑实变量 $t$ 和表达式 $\sum_{i=1}^n (a_i t - b_i)^2$ 。由于它是实数平方和,对任意实数 $t$ 恒有 $\ge 0$ : $\sum(a_i t - b_i)^2 \ge 0$ 。

**第2步:展开为关于 $t$ 的二次式。** 展开得 $\sum (a_i t - b_i)^2 = t^2 \sum a_i^2 - 2t \sum a_i b_i + \sum b_i^2$ 。记 $A = \sum a_i^2$ , $B = \sum a_i b_i$ , $C = \sum b_i^2$ ,则表达式为对任意实数 $t$ 有 $At^2 - 2Bt + C \ge 0$ 。

第3步:处理退化情形。 若 $A = 0$ ,则所有 $a_i = 0$ ,于是待证不等式 $B^2 \le AC$ 两边都是 $0$ ,不等式平凡成立(取等)。

**第4步:当 $A > 0$ 时用判别式。** 首项系数 $A$ 为正的二次式 $At^2 - 2Bt + C$ 若对每个实数 $t$ 都 $\ge 0$ ,则它至多有一个实根,故判别式不能为正: $(2B)^2 - 4AC \le 0$ ,即 $4B^2 \le 4AC$ ,即 $B^2 \le AC$ 。

第5步:结论。 代回得 $\left(\sum a_i b_i\right)^2 \le \left(\sum a_i^2\right)\left(\sum b_i^2\right)$ ,这正是 $\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2$ 。等号成立恰好当判别式为零,即二次式有实重根 $t_0$ ,即对每个 $i$ 都有 $a_i t_0 = b_i$ ——数列 $(a_i)$ 与 $(b_i)$ 成比例。

定理: 舒尔不等式(

r=1

)

对非负实数 $a,b,c$ : $a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b)\ge 0$ ,等号成立当且仅当 $a=b=c$ ,或其中两个相等而第三个为 $0$ 。

为什么成立?

舒尔不等式是应对直接用 AM–GM 或柯西–施瓦茨难以解决的对称三元竞赛不等式的标准终结手段,尤其是同时涉及 $a+b+c$ 、 $ab+bc+ca$ 、 $abc$ 的情形。

证明

第1步:利用对称性化简。 式 $a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b)$ 关于 $a,b,c$ 对称,故不失一般性设 $a \ge b \ge c \ge 0$ 。

第2步:合并前两项。 合并 $a(a-b)(a-c) + b(b-a)(b-c) = (a-b)\big[a(a-c) - b(b-c)\big]$ ,从两项中提出公因子 $(a-b)$ (注意 $b(b-a)(b-c) = -(a-b)\cdot b(b-c)$ )。

第3步:化简括号内。 展开 $a(a-c) - b(b-c) = a^2 - ac - b^2 + bc = (a^2-b^2) - c(a-b) = (a-b)(a+b) - c(a-b) = (a-b)(a+b-c)$ 。

第4步:合并。 代回,合并的项等于 $(a-b)\cdot(a-b)(a+b-c) = (a-b)^2(a+b-c)$ 。于是整个表达式等于 $(a-b)^2(a+b-c) + c(a-c)(b-c)$ (最后一项正是原来的第三项,未变)。

第5步:逐项判号。 因为 $a \ge b \ge c \ge 0$ :恒有 $(a-b)^2 \ge 0$ 。关于 $a+b-c$ 的符号:由 $a \ge c$ 得 $a - c \ge 0$ ,又 $b \ge 0$ ,故 $a+b-c = (a-c)+b \ge 0$ 。因此 $(a-b)^2(a+b-c) \ge 0$ 。对第二部分: $c \ge 0$ , $a-c \ge 0$ (因 $a\ge c$ ), $b - c \ge 0$ (因 $b \ge c$ ),故 $c(a-c)(b-c) \ge 0$ 是三个非负数之积。

第6步:结论。 整个表达式是两个非负项之和, $(a-b)^2(a+b-c) + c(a-c)(b-c) \ge 0$ ,证明了 $r=1$ 时的舒尔不等式。取等要求两部分都为零:或 $a=b$ (使第一项为 $0$ )且 $c(a-c)(b-c)=0$ (若再有 $a=c$ 则 $a=b=c$ ;若 $c=0$ 则 $a=b, c=0$ ),与所述取等条件相符。

进阶实际应用与典型例题

柯西–施瓦茨不仅是竞赛技巧:在信号处理中,它限定了信号与匹配滤波器之间的相关性,给出匹配滤波接收机可达到的最大信噪比(SNR)。在信息论中,詹森不等式(应用于凸函数 $-\log$ )证明了 Kullback–Leibler 散度 $D_{KL}(P\|Q) = \sum p_i \log\frac{p_i}{q_i}$ 恒 $\ge 0$ (吉布斯不等式),这一基础事实使 KL 散度成为概率分布间(尽管不对称)的有效距离度量,是交叉熵等机器学习损失函数的核心。

例题: 通过柯西–施瓦茨的匹配滤波信噪比界限

接收机观测 $y_i = s_i + n_i$ ( $i=1,\dots,n$ ),其中 $s_i$ 是已知信号, $n_i$ 是满足 $\sum n_i^2 \le N$ 的噪声。接收机计算相关值 $\sum s_i y_i$ 。用柯西–施瓦茨限定噪声能使这一相关值偏离多少,即限定 $|\sum s_i n_i|$ 。

解答

第1步:直接对数列 $(s_i)$ 与 $(n_i)$ 应用柯西–施瓦茨: $\left(\sum s_i n_i\right)^2 \le \left(\sum s_i^2\right)\left(\sum n_i^2\right)$ 。

第2步:代入噪声能量界 $\sum n_i^2 \le N$ ,记信号能量 $E_s = \sum s_i^2$ : $\left(\sum s_i n_i\right)^2 \le E_s \cdot N$ 。

第3步:开平方根: $|\sum s_i n_i| \le \sqrt{E_s N}$ 。而无噪声时的相关值恰为 $\sum s_i^2 = E_s$ ,故最坏情形下的相对扰动为 $\frac{\sqrt{E_s N}}{E_s} = \sqrt{N/E_s}$ ——当信号能量 $E_s$ 相对噪声能量 $N$ 越大时越小,这正是信噪比(比值 $E_s/N$ )控制检测可靠性这一直观说法,而柯西–施瓦茨表明匹配滤波器 $s_i$ 实际上是最优相关器(任何其他滤波器都给出更弱的界),因为等号仅在噪声恰好与 $s_i$ 本身成比例时成立。

例题: 通过詹森证明KL散度非负

对概率分布 $p_1,\dots,p_n$ 与 $q_1,\dots,q_n$ (均为正数,和为 $1$ ),证明吉布斯不等式 $D_{KL}(P\|Q) = \sum_i p_i \log\frac{p_i}{q_i} \ge 0$ 。

解答

第1步:重写 $D_{KL}(P\|Q) = -\sum_i p_i \log\frac{q_i}{p_i} = \sum_i p_i \cdot \left(-\log\frac{q_i}{p_i}\right)$ ,识别出这是以 $p_i$ 加权的期望 $\mathbb{E}_{p}\left[-\log \frac{q_i}{p_i}\right]$ 。

第2步:因为 $-\log$ 是凸函数,詹森不等式对任意随机变量 $X$ 给出 $\mathbb{E}[-\log X] \ge -\log \mathbb{E}[X]$ (这里 $X = q_i/p_i$ ,概率为 $p_i$ )。

第3步:计算 $\mathbb{E}[X] = \sum_i p_i \cdot \frac{q_i}{p_i} = \sum_i q_i = 1$ ,因为 $q_i$ 构成概率分布。

第4步:结合得 $D_{KL}(P\|Q) = \mathbb{E}[-\log X] \ge -\log \mathbb{E}[X] = -\log 1 = 0$ ,证明了 $D_{KL}(P\|Q) \ge 0$ ,等号成立当且仅当对所有 $i$ , $q_i/p_i$ 为常数(由严格凸函数 $-\log$ 的詹森等号条件),即当且仅当 $P = Q$ 。

在通过 $\sum(a_i t - b_i)^2 \ge 0$ 的判别式证明柯西–施瓦茨的过程中,用二次式 $At^2-2Bt+C$ 的什么性质来得出 $B^2 \le AC$ ?

舒尔不等式 $a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b)\ge 0$ 在什么样的 $a,b,c$ (除 $a=b=c$ 外)下取等?

Titu 引理 $\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}$ 是通过什么代换从柯西–施瓦茨导出的?

在证明吉布斯不等式 $D_{KL}(P\|Q) \ge 0$ 时,对凸函数 $-\log$ 应用了哪个不等式?

参考文献

J. Michael Steele (2004). The Cauchy-Schwarz Master Class
Radmila Bulajich Manfrino, José Antonio Gómez Ortega, Rogelio Valdez Delgado (2009). Inequalities: A Mathematical Olympiad Approach
Thomas M. Cover, Joy A. Thomas (2006). Elements of Information Theory