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

この記事の所要時間: 311

No.190 Maximising a weighted product

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

問題.

Q.

\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*}

となります.

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

A. 371048281

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加