组合最值

组合最值的标准答案结构分两段：

1. 构造：给出达到该值的一个具体方案；
2. 上界（或下界）证明：任何方案都超不过（或不低于）该值。

两部分缺一不可。猜的途径是试小的情形、抓“最紧的约束”——让最受限的元素先满足，极端构造往往自然浮现。

• 极端原理：取最大、最小、最长、最短的元素下手，它的性质最“硬”；
• 调整法：每步微调不使目标变差，最优方案就落在调整的不动点上（常是“平均”或“极端”形态）；
• 整体计数：用总和的界加抽屉或反证，封住所有方案的天花板。

例1 拆数最大乘积

把 $17$ 拆成若干个正整数之和，使乘积最大。求最大乘积。

解：先看最优拆法长什么样。若某个数是 $1$，把它并入另一个数 $a$：乘积从 $1\times a$ 变为 $a+1$，变大，故最优拆法不含 $1$。若有数 $x\ge 5$，拆成 $3$ 与 $x-3$：$3(x-3)=3x-9\ge x$ 当 $x\ge 5$ 成立（取等仅当 $x=4.5$ 不是整数），且拆开后个数变多还有余地，故最优拆法只含 $2$、$3$、$4$；$4=2+2$ 且 $2\times 2=4$，可全部化为 $2$ 和 $3$；又 $2+2+2=3+3$ 而 $2^3=8$ 小于 $3^2=9$，故 $2$ 至多两个。

$17=3+3+3+3+3+2$，最大乘积 $3^5\times 2=486$。

例2 分割正方形加抽屉

边长为 $1$ 的正方形内（含边界）任取 $5$ 个点，证明其中存在两点距离不超过 ${\displaystyle \frac{\sqrt{2}}{2}}$。

解：把正方形分成 $2\times 2$ 共 $4$ 个边长 ${\displaystyle \frac{1}{2}}$ 的小正方形，每个小正方形的对角线长为 ${\displaystyle \frac{\sqrt{2}}{2}}$。

$5$ 个点落入 $4$ 个小正方形，由抽屉原理必有两点落在同一个小正方形内，它们的距离不超过该格的对角线 ${\displaystyle \frac{\sqrt{2}}{2}}$。

“$n^2$ 个格子、$n^2+1$ 个点”是分割估计的标准配方，格子边长与目标距离靠对角线挂钩。

例3 整体计数封顶

$10$ 个人聚会，“认识”是相互的。证明存在相邻的两人（按圆桌就座顺序），他们认识的人数之和不超过 $9$。

解：设第 $i$ 人认识 $d_i$ 人。认识关系成对出现，总数不超过 $C_{10}^2=45$，故 $\sum d_i\le 45$。

反设每对相邻两人都满足 $d_i+d_{i+1}\ge 10$。沿圆桌把 $10$ 个不等式相加，每个人恰好出现在两条不等式中：

$$2{\sum }_{i=1}^{10}{d}_i\ge 100,\sum d_i\ge 50,$$

与 $\sum d_i\le 45$ 矛盾。所以必存在相邻两人认识人数之和不超过 $9$。整体计数与反证相撞，是“存在一对”型题的固定打法。