一個整數A劃分成n個數，每個數至少等於1，怎樣劃分才能使這n個數的平方和最小？

02-03

直覺告訴我是均分A能達到效果，方法如下：
val = A / n;
rest = A % n;
cnt = n - rest;
ans = cnt * val ^ 2 + rest * (val + 1) ^ 2;

ans就是要求的最小值。
但是我不知道要如何證明其正確性，也不知道其原理根源在哪裡？

假設n個數中存在兩個數a,b, $|a-b|>1$ ,設 $a>b$

那麼 $(a-1)^2+(b+1)^2</P>然後對於某個A，滿足<img src=$ 的劃分是唯一的

over

磨光變換。

假定最優解不是這樣，那麼可以進行微調，得到一個更優解。（參見 @npbool的回答）

於是我們知道，最優解如果存在，必定為均分（各項之間最多相差1）的形式。

又因為最優解必定存在（所有的分法種類數都是有限的，因此下確界一定可以取得），說明均分的方案就是最優解。答案是這樣，證明也很簡單。

首先如果A/n為整數，那麼這就是均值不等式的情況：

$f(vec{x} )=sum_{i=1}^nx^2_igeq n(frac{sum^n_{i=1}x_i}{n})^2=A^2/n$

等號當x_i都相等時取到，即都等於A/n。

如果不是整數，也就是我們會有兩類數，第一類=x，第二類=x+1，

如果我們對這組數進行調整，只有這麼幾種情況：

1. x,x=x-1,x+1;

2.x+1,x+1=x,x+2;

3.x,x+1=x-1,x+2;

4.x,x+1=x+1,x;

對第一種情形，(x-1)^2+(x+1)^2=x^2+x^2+2&>x^2+x^2，

其餘類似，都是遞增的情形，也就是說這組數是一個局部極小，

而f(x)是一個凸函數，局部極小就是全局最小。

既然是問原理不是問證明，那就應該說的本質一點。

簡單的說，原理就是柯西不等式，或者說是平均值不等式，都可以： $a_1^2+a_2^2+cdots+a_n^2geqfrac{1}{n}(a_1+a_2+cdots+a_n)^2$

等號成立條件是這一堆數都相等。

這個不等式換一種說法：當 $a_1+a_2+cdots+a_n$ 這個總和固定的時候，平方和在這一堆數都相等的時候最小。

更本質的說法是 $f(x)=x^2$ 這個函數的凸性，由於這個函數是下凸的，所以 $frac{f(x_1)+f(x_2)}{2}geq f(frac{x_1+x_2}{2})$ ，（請自行腦補函數圖像和左右兩邊在圖像上的位置），由此可得上述平方和與和的平方之間的關係。

以上是宏觀的。至於A不能等分的情況，可逐步微調的辦法處理。

但總體上，由於函數凸性， $a_1^2+a_2^2$ 這個東西是在兩個數接近的時候比較小，兩個數相差較大的時候值比較大。

首先肯定題主的劃分確實是最優劃分，以下給出證明

設有 $x_1 + x_2 + ... + x_n = a \ a~ \%~ n = b ~ ~ 0 leq b < n$

所以我們有 $(a - b) ~\% ~n = 0$

所以按題主的劃分，以下簡稱方案A我們有

$x_1 = x_2 = ... = x_{n - b} = (a -b) /n = v$

$x_{n-b + 1} = x_{n - b + 2} = ... = v + 1$

所以有 $sum_{1}^{n}{x_{i}^2} = (n -b) v^2 + b(v + 1)^2 = nv^2 +2bv + b = n (frac{a - b}{n})^2 + 2bfrac{a-b}{n} + b = frac{(a^2-b^2)}{n} + b$

$=frac{a^2}{n} + frac{nb - b^2}{n}$

設 $x_1, x_2, ..., x_n$ 是 $a$ 的任意一個劃分B，則 $x_i$ 總可以表示成下面的兩個和，即總有：

$x_i = v + a_i$

$a_1 + a_2 + ... + a_n = b$

所以有 $sum_{i = 1}^{n}{x_i^2} = sum_{i = 1}^{n}{(v + a_i)^2} = sum_{i = 1}^{n}{(v^2 + 2va_i + a_i^2)} = nv^2 + 2bv + sum_{i=1}^{n}{a_i^2}$

現在即我們只需證明 $sum_{i= 1}^{n}{a_i^2} geq b$ 即能得出A是最優方案，很明顯當b = 0時該條件成立

當 $b geq 1$ 是我們有，因為 $sum_{i=1}^{n}{(a_i - 1)^2} geq 0$

所以我們有 $sum_{i=1}^{n}{(a_i^2 - 2a_i +1)} geq 0$

所以 $sum_{i=1}^{n}{a_i^2} geq 2b - 1 = b + b - 1 geq b$ (此處有誤)

得證！

------------------------------------------------------------------------------------------------------------

最後一步證明錯了哈，害我一晚上沒睡著，蛋疼啊， $sum_{i=1}^{n}{a_i^2} geq 2b - n = b + b - n$ 這個不能得出上面的結論，但其實可以證明，首先我們假定 $a_1,a_2,...,a_n$ 中只有 $k$ 個不為零，為了討論方便我們先設前 $k-1$ 個為正，最後一個為負，很明顯如果我們將最後一個增大至零，在前 $k-1$ 個數做相應的減少，但仍保持前 $k-1$ 個位正數，此時前 $k-1$ 個數的平方和一定小於變化之前的平方和，我們很容易將這個結論擴展至 $k$ 項中有 $m$ 個為負數的情況，即有：