# 一个有趣的问题

Author: Fanyi Pu

Published: 2019-02-06

Canonical: <https://pufanyi.com/blog/oi-icpc/other-problems/integer-break>

将正整数分解为若干正整数之和，使乘积最大。

把正整数 $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}
$$