反证、构造与结果验证

验证与建模

检查单位、符号、极端情形与小规模实例，能暴露模型错误。数值计算应记录精度，近似相等不能当成恒等证明。应用题还应回到原问题解释变量和答案，例如人数必须为整数、长度必须非负、概率必须在 $[0,1]$ 内。

平均值原理与极端对象的选择

平均值保证某个对象达到什么程度

对实数 $a_1,\ldots,a_n$，记 $m=\min a_i$、$M=\max a_i$。由逐项相加，

因此至少有一个数不小于平均值，至少有一个数不大于平均值。若所有数都严格小于平均值，相加便与平均值的定义矛盾；另一方向相同。当各数不全相等时，两端不等式都严格。

若 $a_i>0$，从 $m^n\le\prod a_i\le M^n$ 开 $n$ 次方，还得到几何平均位于 $m,M$ 之间。若 $a_i\ge0$，从 $nm^2\le\sum a_i^2\le nM^2$ 开方，得到平方平均也位于二者之间。平方平均的这个表述不能直接用于任意负数，例如 $a_1=a_2=-1$ 时平方平均是 $1$，已大于最大项。

在计数中，若 $n$ 个对象的整数得分总和为 $S$，便有某个得分至少为 $\lceil S/n\rceil$，也有某个至多为 $\lfloor S/n\rfloor$。证明时先求总体数量，再由平均分配得到某个对象的保证，通常不必先找到该对象。

加权平均的最大、最小界

若 $p_i\ge0$ 且 $P=\sum_{i=1}^n p_i>0$，则

证明是将 $m\le a_i\le M$ 乘以 $p_i$ 后求和，再除以 $P$。左侧等号当且仅当每个 $p_i>0$ 的项均满足 $a_i=m$；右侧等号同理。权重为零的项不影响平均值；允许负权重时结论一般不成立，例如权重 $2,-1$ 对数值 $1,0$ 给出平均值 $2$，超过最大项 $1$。

极端原理的使用步骤

非空有限实数集一定能取到最大值和最小值：依次比较两个数、保留较大者，有限次后得到最大值；最小值同理。证明中据此选择长度最短、得分最高、关联对象最少等对象，再利用“它不可能被合法对象进一步改进”的约束。

使用时应明确三件事：候选对象集合为何非空；所比较的量为何取到最值；改变对象后是否仍满足候选条件。对无限集合不能直接套用有限性结论，例如 $(0,1)$ 没有最大元也没有最小元。若依靠正整数的最小数原理，应明确比较量是正整数，而不是笼统地称“取最小”。

最值证明要同时给出界和达到界的对象

若目标是最大值 $M$，须证明所有合法对象的值都不超过 $M$，再构造一个合法对象恰取 $M$；最小值则反向。只有上界不能证明最大值，只有一个较好的构造也不能排除更好者。若只能构造一列值趋近 $M$ 而无人达到，应称为上确界，并明确最大值不存在。