题解 P4157 【[SCOI2006]整数划分】

· · 题解

以下纯口胡，如果问题求私信我。

根据均值不等式（证明在最下面）：

\prod_{i=1}^n x_i\le \left(\frac{\sum_{i=1}^nx_i}{n}\right)^n

先不考虑整数的限制，我们应将一个数均匀地分成k份，每个数为x，那么有：

n=kx

另乘积为y，有：

y=x^k=x^{\frac{n}{x}}=(x^{\frac{1}{x}})^n

于是问题就变成了求y=x^{\frac{1}{x}}在x>0上的极值。

两边同取对数：

\ln y = \frac{1}{x}\ln x

两边同时关于x求导：

\frac{y'}{y}=-\frac{1}{x^2}\ln x+\frac{1}{x^2}=\frac{1-\ln x}{x^2}

右边应该没问题，那左边为什么不是\frac{1}{y}呢？

因为y是个因变量，其导数不一定就是1，即x增加\mathrm{d}x，y不一定增加\mathrm{d}x。

但我们有：

f[g(x)]=f'(x)g'(x)

于是：

y'=\frac{1-\ln x}{x^2}y=\frac{1-\ln x}{x^2}x^{\frac{1}{x}}

当y'=0时：

\frac{1-\ln x}{x^2}x^{\frac{1}{x}}=0

由于x>0：

1-\ln x=0

即：

x=e

但e不是整数，由于\lfloor e\rfloor=2,\lceil e\rceil=3，且

2^{\frac{1}{2}}\approx1.4142135623730950488016887242097 3^{\frac{1}{3}}\approx1.4422495703074083823216383107801

所以

2^{\frac{1}{2}}<3^{\frac{1}{3}}

因此应该尽量取3，多出来的取2。

下面给出均值不等式的一种证法：

有一种叫“反向归纳法”的东西，它是从n到n-1来证明命题。

我们令原命题为P(n)。

首先，n=2时显然为真：

\sqrt{ab}\le \frac{a+b}{2}

然后证明P(n)和P(2)蕴涵着P(2n)：

因为：

\prod_{i=1}^n x_i\le \left(\frac{\sum_{i=1}^nx_i}{n}\right)^n \prod_{i=n+1}^{2n} x_i\le \left(\frac{\sum_{i=n+1}^{2n}x_i}{n}\right)^n

两式相乘：

\prod_{i=1}^{2n} x_i\le \left(\frac{\sum_{i=1}^{n}x_i}{n}\right)^n\times\left(\frac{\sum_{i=n+1}^{2n}x_i}{n}\right)^n\le \left(\frac{\sum_{i=1}^{2n}x_i}{2n}\right)^{2n}

最后证明P(n)蕴涵着P(n-1)：

令x_n=\frac{\sum_{i=1}^{n-1}x_i}{n-1}即x_n为前n-1项的平均值，我们发现这n项的平均值为前n-1项的平均值，即：

\prod_{i=1}^{n-1} x_i\times\frac{\sum_{i=1}^{n-1}x_i}{n-1}\le \left(\frac{\sum_{i=1}^{n-1}x_i}{n-1}\right)^n

两边同除\frac{\sum_{i=1}^{n-1}x_i}{n-1}：

\prod_{i=1}^{n-1} x_i \le \left(\frac{\sum_{i=1}^{n-1}x_i}{n-1}\right)^{n-1}