一个有趣的问题


2019-02-06

把正整数 \(n\) 分解成几个正整数的和,是它们的乘积最大。

以下纯口胡,如果有问题求在下面留言。

根据均值不等式(证明在最下面):

\[ \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} \]

Cite this post

@misc{pu2019integerbreak,
  author = {Pu, Fanyi},
  title  = {一个有趣的问题},
  year   = {2019},
  month  = {2},
  url    = {https://pufanyi.com/blog/integer-break}
}