プロジェクトオイラー190.

この記事の所要時間：約 3分11秒

No.190 Maximising a weighted product

以前の記事「自作問題22」でも紹介した, 条件付きの関数の極値の必要条件の定理が使える問題があったので紹介します.

問題.

$\begin{align*} S_m = (x_1, x_2, \ldots, x_m) \end{align*}$

は $m$ 個の正の実数の組で,

$\begin{align*} x_1+x_2+\cdots+x_m=m \end{align*}$

を満たした上で

$\begin{align*} P_m=x_1\times x_2^2\times\cdots\times x_m^m \end{align*}$

の値を最大化している. 例えば,

$\begin{align*} [P_{10}]=4112 \end{align*}$

(ここで, []は整数部分をとる関数)になります.では

$\begin{align*} \sum_{m=2}^{15}[P_m] \end{align*}$

の値はいくつか.

考え方とプログラム例(Python).

例の定理を使うので,

$\begin{align*} f(x) &= x_1x_2^2\cdots x_m^m\\ \phi(x) &= x_1+x_2+\cdots+x_m-m \end{align*}$

とおきます.

$\phi(x)$ の勾配は

$\begin{align*} \grad{\phi}=\left(\begin{array}{l}1\\1\\ \vdots\\1\end{array}\right)\neq\boldmath{0} \end{align*}$

なので,

$\begin{align*} \nabla{f}=\lambda\nabla{\phi} \end{align*}$

を考えます.

$\grad{f}$ を考えると,

$\begin{align*} \left(\begin{array}{c}P_m/x_1\\ 2P_m/x_2\\ \vdots\\ mP_m/x_m\end{array}\right)=\lambda\left(\begin{array}{l}1\\1\\\vdots\\1\end{array}\right) \end{align*}$

となるので,

$\begin{align*} 1/x_1=2/x_2=\cdots=m/x_m \end{align*}$

これと $\phi(x)=0$ から,

$\begin{align*} x_i=\frac{2i}{m+1} \quad(i=1,2,\ldots,m) \end{align*}$

と求まるので

$\begin{align*} P_m &= \prod_{i=1}^m \left(\frac{2i}{m+1}\right)^i\\ &= \left(\frac{2}{m+1}\right)^m\prod_{i=1}^m i^i \end{align*}$

となります.

Sum = 0
for m in xrange(2, 16):
	P = 1.0
	for j in xrange(1, m+1):
		P *= j ** j
	P *= 2 ** (m * (m + 1)/2)
	P /= (m+1) ** (m * (m + 1)/2)
	Sum += int(P)
print Sum

Sum = 0

for m in xrange(2, 16):

P = 1.0

for j in xrange(1, m+1):

P *= j ** j

P *= 2 ** (m * (m + 1)/2)

P /= (m+1) ** (m * (m + 1)/2)

Sum += int(P)

print Sum

答えはこの下の行にあります. 反転してください.

A. 371048281

プロジェクトオイラー190.

No.190 Maximising a weighted product

問題.

考え方とプログラム例(Python).

共有:

関連

関連記事

微分せずに相加相乗平均の関係から最小値を求める練習