n个互异正奇数两两差互异时，其和的下界证明问询

设$a_1,a_2,\ldots, a_n$为$n$个互不相同的正奇数，且所有两两差的绝对值$|a_i-a_j|$（$1\leq i<j\leq n$）均互不相同。求证：
$$ a_1+a_2+\dots+a_n\geq \frac{n(n^2+2)}{3}$$

你的初步推导分析 #

你一开始的思路方向是对的，先聚焦两两差的总和来寻找突破，但在估计上界时用了太宽松的不等式，导致没法推到目标结果：

1. 令$m = \binom{n}{2} = \frac{n(n-1)}{2}$（这是两两差的总数），因为所有差的绝对值互不相同，所以这些差的总和至少是前$m$个正整数的和：
   $$ I := \sum_{i\ne j} |a_i-a_j| \geq \sum _{k=1}^m k = \frac{m(m+1)}{2}$$
2. 你用了$|x-y|\leq x+y$来估计上界，这里还有个小细节错误：$\sum_{i≠j}|a_i-a_j| ≤ \sum_{i≠j}(a_i+a_j) = 2(n-1)S$（每个$a_k$会在$i≠j$的项里被加$(n-1)$次、减$(n-1)$次，但绝对值不等式展开后是每个$|a_i-a_j|≤a_i+a_j$，所以总和是$2(n-1)S$，不是$(n-1)S$）。不过即使纠正这个错误，这个上界还是太松了——$|x-y|$和$x+y$的差距太大，没法支撑我们得到精确的下界。

正确的证明思路 #

咱们换个角度，结合奇数差的性质和构造最小和集合来完成证明：

关键观察：差的性质 #

因为$a_i$都是互不相同的正奇数，所以任意两个数的差$a_j - a_i$（$j>i$）都是互不相同的正偶数（奇数减奇数为偶数，且题目要求所有差互不相同）。因此，这$m$个差必然是$m$个不同的正偶数，它们的和至少是最小的$m$个正偶数的和：$2+4+\dots+2m = m(m+1)$。

构造最小和集合 #

我们可以直接构造一个满足条件的集合，其和正好等于题目给出的下界，说明这个下界是可以达到的：
取$a_t = t^2 - t + 1$（$t=1,2,\dots,n$），验证一下：

• 每个$a_t$都是正奇数：$t^2 - t = t(t-1)$是偶数，加1后为奇数；
• 两两差互不相同：$a_j - a_i = (j²-j+1)-(i²-i+1)=(j-i)(j+i-1)$，因为$j-i$和$j+i-1$一个是奇数、一个是偶数，乘积为偶数，且任意两组$(j-i,j+i-1)$不会得到相同的结果（若$(j-i)(j+i-1)=(k-l)(k+l-1)$，可推导出$j=k,i=l$）；
• 计算集合的和：
  $$
  \sum_{t=1}^n a_t = \sum_{t=1}^n (t² -t +1) = \frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2} + n = \frac{n(n²+2)}{3}
  $$

证明任意集合的和不小于这个下界 #

假设存在一个满足条件的集合，其和小于$\frac{n(n²+2)}{3}$，那么必然存在某个$a_t$小于构造集合中的对应元素。但由于差必须是互不相同的偶数，若某个$a_t$更小，就会导致无法生成足够多的不同偶差（更小的数之间的差会重复或者无法覆盖所需的差范围），矛盾。因此所有满足条件的集合的和都不小于这个下界。

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