空间中有 $1989$ 个点，其中任何三点不共线，把它们分成点数各不相同的 $30$ 组，在任何三个不同的组中各取一点为顶点作三角形．问：要使这种三角形的总数最大，各组的点数应为多少？
【难度】
【出处】
1989第4届CMO试题
【标注】
【答案】
略
【解析】
把 $1989$ 个点分成 $30$ 组，各组的点数记为 $n_{1}, \cdots, n_{30}$ 时，在任何三个不同的组中各取一点为顶点作三角形，则这种三角形的总数为 $\displaystyle \sum\limits_{1 \leqslant i<j<k \leqslant 30} n_{i} n_{j} n_{k}$．
由于总共只有有限种分法，因为使所作三角形总数最大的分法必定存在．如果把一种分法的两组点数改动，其余各组不变，不妨设各组点数为 $n_{1}^{\prime}, n_{2}^{\prime}, \cdots, n_{30}^{\prime}$，而 $n_{i}^{\prime}=n_{i}(i=3,4, \cdots, 30)$．由于
$\displaystyle \sum\limits_{1 \leqslant i<j<k \leqslant 30} n_{i} n_{j} n_{k}=\left(\sum_{k=3}^{30} n_{k}\right) n_{1} n_{2}+\left(\sum_{3 \leqslant j<k \leqslant 30} n_{j} n_{k}\right)\left(n_{1}+n_{2}\right)+\sum_{3 \leqslant i<j<k \leqslant 30} n_{i} n_{j} n_{k} \sum_{1 \leqslant i<j<k \leqslant 30} n_{i}^{\prime} n_{j}^{\prime} n_{k}^{\prime}\\=\left(\sum_{k=3}^{30} n_{k}^{\prime}\right) n_{1}^{\prime} n_{2}^{\prime}+\left(\sum_{3 \leqslant j<k \leqslant 30} n^{\prime} n^{\prime}_{k}\right)\left(n_{1}^{\prime}+n_{2}^{\prime}\right)+\sum_{3 \leqslant i<j<k \leqslant 30} n_{i}^{\prime} n_{j}^{\prime} n_{k}^{\prime}\\=\left(\sum_{k=3}^{30} n_{k}\right) n_{1}^{\prime} n_{2}^{\prime}+\left(\sum_{3 \leqslant j<k \leqslant 30} n_{j} n_{k}\right)\left(n_{1}+n_{2}\right)+\sum_{3 \leqslant i<j<k \leqslant 30} n_{i} n_{j} n_{k}$
因为 $n_{1}+n_{2}=n_{1}^{\prime}+n_{2}^{\prime}$，因此，如果 $\left|n_{2}^{\prime}-n_{1}^{\prime}\right|<\left|n_{2}-n_{1}\right|$ 就有 $\displaystyle \sum\limits_{1 \leqslant i<j<k \in 30} n_{i} n_{j} n_{k}<\sum_{1 \leqslant i<j<k \leqslant 30} n_{i}^{\prime} n_{j}^{\prime} n_{k}^{\prime}$ 现设各组点数为 $n_{1}, \cdots, n_{30}$ 时，所作三角形总数最大，由于要求各组点数都不同，不妨设 $n_{1}<n_{2}<\cdots<n_{30}$．由上所述，可得到 $n_{1}, \cdots, n_{30}$ 必须有下列性质：
（1）对于任何 $k(1 \leqslant k \leqslant 29), n_{k+1}-n_{k} \leqslant 2$．
如果某一个 $k_0$ 使 $n_{k_{0}+1}-n_{k_{0}} \geqslant 3$，则取 $n^{\prime} k_{0}=n_{k_{0}}+1, n_{k_{0}+1}^{\prime}=$ $n_{k_{0}+1}-1\left(n_{i}^{\prime}=n_{i}, \stackrel{s l}{\jmath} i \neq k_{0}, k_{0}+1\right)n_{k_{0}+1}-1\left(n_{i}^{\prime}=n_{i}, 当 i \neq k_{0}, k_{0}+1\right)$，即在第 $k_{0}+1$ 组中把一个点放入第 $k_{0}$ 组，将使所作三角形总数确实增大．
（2）使得 $n_{k+1}-n_{k}=2$ 的 $k$ 至多只有一个．
如果有二个 $i,j$（不妨设 $1 \leqslant i<j<29$）使得 $n_{i+1}-n_{i}=2,n_{j+1}-n_{j}=2$．这时取 $n_{j+1}^{\prime}=n_{j+1}-1, n_{i}^{\prime}=n_{i+1}$（其余各组点数不变），这样将使所作三角形总数确实增大．
由于 $\sum_{i=1}^{30} n_{i}=1989$，因此不可能 $n_{k+1}-n_{k}=1, k=1,2, \cdots, 29$（否则这 $30$ 个数是等差数列，其和应为 $15$ 的倍数，但 $15\not |1989$）．因而恰有一个 $k_0$ 使 $n_{k_{0}+1}-n_{k_{0}}=2$．这 $30$ 个数为 $n_{1}, n_{1}+1, \cdots, n_{1}+k_{0}-1, n_{1}+k_{0}+1, \cdots, n_{1}+30$ 于是 $ 1989+k_{0}= \dfrac{1}{2} \cdot 30\left(n_{1}+1+n_{1}+30\right)= 15\left(2 n_{1}+31\right) $ 解得 $k_{0}=6, n_{1}=51$ 所求的各组点数为 $51,52, \cdots, 56,58,59, \cdots, 81$．
由于总共只有有限种分法，因为使所作三角形总数最大的分法必定存在．如果把一种分法的两组点数改动，其余各组不变，不妨设各组点数为 $n_{1}^{\prime}, n_{2}^{\prime}, \cdots, n_{30}^{\prime}$，而 $n_{i}^{\prime}=n_{i}(i=3,4, \cdots, 30)$．由于
$\displaystyle \sum\limits_{1 \leqslant i<j<k \leqslant 30} n_{i} n_{j} n_{k}=\left(\sum_{k=3}^{30} n_{k}\right) n_{1} n_{2}+\left(\sum_{3 \leqslant j<k \leqslant 30} n_{j} n_{k}\right)\left(n_{1}+n_{2}\right)+\sum_{3 \leqslant i<j<k \leqslant 30} n_{i} n_{j} n_{k} \sum_{1 \leqslant i<j<k \leqslant 30} n_{i}^{\prime} n_{j}^{\prime} n_{k}^{\prime}\\=\left(\sum_{k=3}^{30} n_{k}^{\prime}\right) n_{1}^{\prime} n_{2}^{\prime}+\left(\sum_{3 \leqslant j<k \leqslant 30} n^{\prime} n^{\prime}_{k}\right)\left(n_{1}^{\prime}+n_{2}^{\prime}\right)+\sum_{3 \leqslant i<j<k \leqslant 30} n_{i}^{\prime} n_{j}^{\prime} n_{k}^{\prime}\\=\left(\sum_{k=3}^{30} n_{k}\right) n_{1}^{\prime} n_{2}^{\prime}+\left(\sum_{3 \leqslant j<k \leqslant 30} n_{j} n_{k}\right)\left(n_{1}+n_{2}\right)+\sum_{3 \leqslant i<j<k \leqslant 30} n_{i} n_{j} n_{k}$
因为 $n_{1}+n_{2}=n_{1}^{\prime}+n_{2}^{\prime}$，因此，如果 $\left|n_{2}^{\prime}-n_{1}^{\prime}\right|<\left|n_{2}-n_{1}\right|$ 就有 $\displaystyle \sum\limits_{1 \leqslant i<j<k \in 30} n_{i} n_{j} n_{k}<\sum_{1 \leqslant i<j<k \leqslant 30} n_{i}^{\prime} n_{j}^{\prime} n_{k}^{\prime}$ 现设各组点数为 $n_{1}, \cdots, n_{30}$ 时，所作三角形总数最大，由于要求各组点数都不同，不妨设 $n_{1}<n_{2}<\cdots<n_{30}$．由上所述，可得到 $n_{1}, \cdots, n_{30}$ 必须有下列性质：
（1）对于任何 $k(1 \leqslant k \leqslant 29), n_{k+1}-n_{k} \leqslant 2$．
如果某一个 $k_0$ 使 $n_{k_{0}+1}-n_{k_{0}} \geqslant 3$，则取 $n^{\prime} k_{0}=n_{k_{0}}+1, n_{k_{0}+1}^{\prime}=$ $n_{k_{0}+1}-1\left(n_{i}^{\prime}=n_{i}, \stackrel{s l}{\jmath} i \neq k_{0}, k_{0}+1\right)n_{k_{0}+1}-1\left(n_{i}^{\prime}=n_{i}, 当 i \neq k_{0}, k_{0}+1\right)$，即在第 $k_{0}+1$ 组中把一个点放入第 $k_{0}$ 组，将使所作三角形总数确实增大．
（2）使得 $n_{k+1}-n_{k}=2$ 的 $k$ 至多只有一个．
如果有二个 $i,j$（不妨设 $1 \leqslant i<j<29$）使得 $n_{i+1}-n_{i}=2,n_{j+1}-n_{j}=2$．这时取 $n_{j+1}^{\prime}=n_{j+1}-1, n_{i}^{\prime}=n_{i+1}$（其余各组点数不变），这样将使所作三角形总数确实增大．
由于 $\sum_{i=1}^{30} n_{i}=1989$，因此不可能 $n_{k+1}-n_{k}=1, k=1,2, \cdots, 29$（否则这 $30$ 个数是等差数列，其和应为 $15$ 的倍数，但 $15\not |1989$）．因而恰有一个 $k_0$ 使 $n_{k_{0}+1}-n_{k_{0}}=2$．这 $30$ 个数为 $n_{1}, n_{1}+1, \cdots, n_{1}+k_{0}-1, n_{1}+k_{0}+1, \cdots, n_{1}+30$ 于是 $ 1989+k_{0}= \dfrac{1}{2} \cdot 30\left(n_{1}+1+n_{1}+30\right)= 15\left(2 n_{1}+31\right) $ 解得 $k_{0}=6, n_{1}=51$ 所求的各组点数为 $51,52, \cdots, 56,58,59, \cdots, 81$．
答案
解析
备注
