一些不等式问题

Published: by Creative Commons Licence

  • Tags:

最小和最大乘积问题

考虑这样一个问题,你需要给出$n$个非负整数$x_1,x_2,\ldots, x_n$,要求它们的和为$m$,算最大乘积: \(\prod_{i=1}^nx_i\)

直观感觉,当$x_i$取$m/n$时可以得到最优解,但是如果$m$不能被$n$整除,就不发保证得到的是整数了。

命题1:当乘积最大时,$n$个给出的整数中最大值和最小值的差小于等于1

证明:

非常简单,假设整数中最大值为b,而最小值为a,且$b > a + 1$,那么有:

\[(b-1)(a+1)=ab+b-a-1>ab\]

因此我们将$b$替换为$b-1$,而将$a$替换为$a+1$,那么就可以得到更优解,这与假设相悖,因此命题成立。

同理我们可以稍微转换一下问题:我们需要给出$n$个非负整数$x_1,x_2,\ldots, x_n$,要求在它们的乘积至少为$m$的前提下,和尽可能小。

我们知道随着n个整数的和的增大,它们可以严格给出更大的乘积,因此,我们可以二分并检查问题即可,当然这样的时间复杂度为$O(\log_2n\log_2m)$。

事实上,我们知道在最优解中,每个整数的取值落在区间 \([\lfloor m^{1/n}\rfloor, \lceil m^{1/n} \rceil]\) 中,因此我们先令将每个数都取$\lfloor m^{1/n}\rfloor$,之后比较乘积,如果不等,我们就不断将$\lfloor m^{1/n}\rfloor$替换为$\lceil m^{1/n} \rceil$即可,直到最终使得乘积大于m为止。这样时间复杂度为$O(\log_2m)$。

当元素大于等于2时,总和一定小于等于总乘积

命题:当$\forall i(a_i\geq 2)$的时候,一定有$\sum_{i=1}^na_i\leq \prod_{i=1}^na_i$。

我们不妨认为$a_1\leq a_2\leq\ldots \leq a_n$,那么利用归纳法我们进行如下证明:

当$n=1$的时候,命题显然成立。假设当$n<k$的时候命题恒成立,那么当$n=k$的时候,有

\[\prod_{i=1}^na_i=a_n\prod_{i=1}^{n-1}a_i\geq a_n\sum_{i=1}^{n-1}a_i\\ \geq 2(n-1)a_n\geq na_n\geq \sum_{i=1}^na_i\]

因此命题恒成立。

总和一定时最小化平方和

给定$n$个实数未知数$x_1,\ldots,x_n$,要求为这些未知数赋值,满足$\sum_{i=1}^nx_i=S$,且最小化$\sum_{i=1}^nx_i^2$,其中$S\geq 0$。

可以直接给出思路,当$x_1=\ldots=x_n=\frac{S}{n}$时,$\sum_{i=1}^nx_i^2$最小。证明如下:

假设$x_i<x_j$,那么考虑一个很小的正数$\delta$,满足$x_i+\delta\leq x_j-\delta$,那么有

\[(x_i+\delta)^2+(x_j-\delta)^2=x_i^2+x_j^2+2\delta^2+2\delta(x_i-x_j)\\ =x_i^2+x_j^2+2\delta(x_i-x_j+\delta)\]

考虑到$2\delta(x_i-x_j+\delta)<0$,因此我们在满足$\sum_{i=1}^nx_i=S$的前提下,减小了$\sum_{i=1}^nx_i^2$。即原先的赋值方案不是最优的,从而得到最优的赋值方案一定满足所有未知数相等。