如何解决最大化跨组对战数的组合学分组问题？

首先我们把问题转化为更易分析的数学形式：

总共有$n$个人，任意两人要么在同组（组内，不产生对战）要么在不同组（组间，产生对战）。总可能的两人配对数是固定的：$\binom{n}{2} = \frac{n(n-1)}{2}$。所以最大化对战次数等价于最小化所有组内的配对数之和。

步骤1：组内配对数的数学表达 #

假设我们把$n$人分成$m$组（$2 \leq m \leq k$），各组人数为$a_1, a_2, ..., a_m$（满足$a_1+a_2+...+a_m = n$，且每个$a_i \geq 1$）。

组内配对数的总和$S$可以写成：
$$
S = \sum_{i=1}^m \binom{a_i}{2} = \sum_{i=1}^m \frac{a_i(a_i-1)}{2}
$$
展开后化简：
$$
S = \frac{1}{2}\left( \sum_{i=1}^m a_i^2 - \sum_{i=1}^m a_i \right) = \frac{1}{2}\left( \sum_{i=1}^m a_i^2 - n \right)
$$
因为$n$是固定值，所以最小化$S$等价于最小化各组人数的平方和$\sum a_i^2$。

步骤2：固定分组数时，平均分组的平方和最小 #

我们用调整法来证明：假设存在两组人数$x$和$y$，其中$x > y + 1$（两组人数差大于1）。如果把$x$组的1人移到$y$组，得到新的人数$x-1$和$y+1$，此时平方和的变化为：
$$
(x-1)^2 + (y+1)^2 - (x^2 + y^2) = x^2 - 2x + 1 + y^2 + 2y + 1 - x^2 - y^2 = 2(y - x + 1)
$$
因为$x > y + 1$，所以$y - x + 1 < 0$，即调整后的平方和更小。

这说明：只要有两组人数差超过1，我们就能通过调整让平方和变小。直到所有组的人数最多相差1时，平方和达到最小值。

步骤3：分组数越多，平方和越小 #

接下来证明：在允许的范围内（最多$k$组），分组数越多，最小平方和越小。

假设当前有$m$组（$m < k$），我们把其中一个人数$\geq 2$的组拆成1人和$a_i - 1$人，此时平方和的变化为：
$$
1^2 + (a_i - 1)^2 - a_i^2 = 1 + a_i^2 - 2a_i + 1 - a_i^2 = 2 - 2a_i
$$
因为$a_i \geq 2$，所以$2 - 2a_i \leq -2 < 0$，即拆分后平方和变小。

这意味着：分组数越多，平方和越小，对应的组内配对数越少，对战次数就越多。因此最优的分组数是允许的最大值$k$。

结论：最优分组方式 #

结合上面两点，最优策略就是：

• 分成最多允许的$k$组；
• 让各组人数尽可能平均：计算$q = n // k$（商），$r = n % k$（余数），则有$r$组的人数为$q+1$，剩下的$k - r$组人数为$q$。

验证示例 #

比如题目中的$n=6, k=3$：
$q=6//3=2$，$r=0$，所以3组各2人。组内配对数总和为$3 \times \binom{2}{2} = 3$，总配对数$\binom{6}{2}=15$，对战次数$15-3=12$，和示例结果一致。

再举个例子：$n=7, k=3$，$q=2$，$r=1$，即1组3人，2组2人。组内配对数总和为$\binom{3}{2} + 2 \times \binom{2}{2} = 3 + 2 =5$，对战次数$21-5=16$，这是所有可能分法中的最大值。

内容的提问来源于stack exchange，提问作者Allen Walker