Project Euler 190

题目

Maximising a weighted product

Let $S_m=(x_1,x_2,\dots ,x_m)$ be the $m$-tuple of positive real numbers with $x_1+x_2+\cdots +x_m=m$ for which $P_m=x_1\ast x_2^2\ast \cdots \ast x_m^m$ is maximised.

For example, it can be verified that $[P_{10}]=4112$ ([ ] is the integer part function).

Find $\sum [P_m]$ for $2\le m\le 15$.

拉格朗日乘数法

拉格朗日乘数法（等式约束，与不等式约束相对）用于求多元函数在一定约束下的极值。拉格朗日乘数法可以将一个 $n$ 元函数和 $k$ 个约束条件的最优化问题转化成一个解 $n+k$ 元方程组的解的问题。引入的一组新参数 $\lambda$，称为拉格朗日乘数。

令 $f(x_1,x_2,\dots ,x_n)$ 为需要求极值的多元函数，$g_1(x_1,x_2,\dots ,x_n)=0$,$\dots$ 为 $k$ 个等式的约束，那么构造以下 $n+k$ 元拉格朗日函数：

$$\mathcal{L}(x_1,x_2,\dots ,x_n,{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k)=f(x_1,x_2,\dots ,x_n)-\sum _{i=1}^k{\lambda }_i{g}_i(x_1,x_2,\dots ,x_n)$$

问题转化成对函数 $\mathcal{L}$ 求极值。

解决方案

令 $f(x_1,x_2,\dots ,x_m)=\prod _{i=1}^m{x}_i^i,g(x_1,x_2,\dots ,x_m)=\sum _{i=1}^m{x}_i-m$。

那么利用拉格朗日乘数法，构造拉格朗日函数：

$$\mathcal{L}(x_1,x_2,\dots ,x_n,\lambda )=f(x_1,x_2,\dots ,x_n)-\lambda g(x_1,x_2,\dots ,x_n)=\prod _{i=1}^m{x}_i^i-\lambda (\sum _{i=1}^m{x}_i-m)$$

为求最大值，对每个 $x_i$ 求偏导数，有

$${\displaystyle \frac{\partial \mathcal{L}}{\partial x_i}}={\displaystyle \frac{i\cdot f(x_1,x_2,\dots ,x_n)}{x_i}}-\lambda$$

令 ${\displaystyle \frac{\partial \mathcal{L}}{\partial x_i}}=0$，得到 $x_i={\displaystyle \frac{i\cdot f(x_1,x_2,\dots ,x_n)}{\lambda }}$。

由这个式子不难发现，$x_i$ 的值，都是按比例分配的，即 $\mathrm{\forall }i,j\in [1,m],{\displaystyle \frac{x_i}{x_j}}={\displaystyle \frac{i}{j}}$。

因此根据 $g$ 这个约束，可以得到最大值点为 $x_i={\displaystyle \frac{2i}{m+1}}$。

代码

N = 15
ans = 0
for m in range(2, N + 1):
    w = 1
    for i in range(1, m + 1):
        w *= (2 * i / (m + 1)) ** i
    ans += int(w)
print(ans)