For each integer \(m\) from 2 through 15, define
$$P_m=\max \left\{x_1^1x_2^2\cdots x_m^m : x_1+x_2+\cdots+x_m=m,\ x_i \gt 0\right\}.$$
The exponents \(1,2,\dots,m\) make the variables asymmetric: increasing a large-index variable matters much more than increasing a small-index one. The task is to determine the maximizing configuration for every \(m\), take \(\lfloor P_m\rfloor\), and add those integer parts.
This problem looks like a many-variable nonlinear search, but the structure is very rigid. The maximizing point is forced to be proportional to the weight vector \((1,2,\dots,m)\), so the entire problem collapses to a closed formula.
Because the logarithm is strictly increasing, maximizing \(P_m\) is equivalent to maximizing
$$F(x_1,\dots,x_m)=\log P_m=\sum_{i=1}^{m} i\log x_i$$
under the same linear constraint \(x_1+\cdots+x_m=m\).
This reformulation is useful for two reasons. First, it turns a product into a sum, so differentiation becomes straightforward. Second, the Hessian is diagonal:
$$\frac{\partial^2 F}{\partial x_i^2}=-\frac{i}{x_i^2},\qquad \frac{\partial^2 F}{\partial x_i\partial x_j}=0 \quad (i\ne j).$$
Every diagonal entry is negative on the feasible region \(x_i \gt 0\), so \(F\) is strictly concave. That means any interior critical point is automatically the unique global maximum. The boundary cannot maximize the product either, because if some \(x_i\to 0^+\), then \(i\log x_i\to -\infty\).
Introduce a Lagrange multiplier \(\lambda\) for the constraint and consider
$$\mathcal{L}(x_1,\dots,x_m,\lambda)=\sum_{i=1}^{m} i\log x_i-\lambda\left(\sum_{i=1}^{m}x_i-m\right).$$
Differentiating with respect to each \(x_i\) gives
$$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{i}{x_i}-\lambda=0,$$
so every optimal coordinate must satisfy
$$x_i=\frac{i}{\lambda}.$$
This is the decisive structural fact: the maximizing coordinates are not arbitrary; they must scale linearly with the exponents. A variable with weight \(i\) receives \(i\) times as much mass as the variable with weight 1.
Now impose the constraint:
$$\sum_{i=1}^{m}x_i=\frac{1}{\lambda}\sum_{i=1}^{m}i=\frac{1}{\lambda}\cdot\frac{m(m+1)}{2}=m.$$
Hence
$$\lambda=\frac{m+1}{2},\qquad x_i^*=\frac{2i}{m+1}\quad (1\le i\le m).$$
Substituting the maximizing coordinates back into the product gives
$$P_m=\prod_{i=1}^{m}\left(\frac{2i}{m+1}\right)^i.$$
It is often convenient to separate the common denominator:
$$P_m=\frac{2^{1+2+\cdots+m}\prod_{i=1}^{m} i^i}{(m+1)^{1+2+\cdots+m}}=\frac{2^{m(m+1)/2}\prod_{i=1}^{m} i^i}{(m+1)^{m(m+1)/2}}.$$
The implementations do not multiply this expression directly. Instead they use the numerically safer identity
$$\log P_m=\sum_{i=1}^{m} i\log\left(\frac{2i}{m+1}\right),$$
and apply the exponential only once at the end.
For \(m=10\), the maximizing point is
$$\left(\frac{2}{11},\frac{4}{11},\frac{6}{11},\dots,\frac{20}{11}\right).$$
The maximal product is therefore
$$P_{10}=\prod_{i=1}^{10}\left(\frac{2i}{11}\right)^i.$$
Evaluating the logarithmic form gives a value whose integer part is
$$\lfloor P_{10}\rfloor=4112.$$
This is a useful checkpoint because it validates both the derivation and the floating-point rounding behavior used by the implementation.
The C++, Python, and Java implementations all use the closed-form optimizer above rather than performing any search. For each \(m\), they loop through \(i=1,2,\dots,m\), compute the optimal coordinate \(x_i=\frac{2i}{m+1}\), and accumulate the logarithmic contribution \(i\log x_i\). After the loop, one exponential reconstructs \(P_m\).
That log-domain evaluation is the central numerical idea. The direct product contains many powers and can lose accuracy if multiplied naively, while the sum of logarithms stays in a moderate range and preserves the exact maximizing formula derived from the mathematics.
Once the numerical value of \(P_m\) has been reconstructed, the implementation takes its floor. A tiny positive guard such as \(10^{-12}\) is added before converting to an integer so that a value that should be an integer, but is stored as something like \(4111.999999999999\), is not rounded down incorrectly.
The final answer is obtained by repeating this process for \(m=2,3,\dots,15\) and summing the floors. One implementation also checks the known intermediate value \(\lfloor P_{10}\rfloor=4112\) before performing the full accumulation.
For a single value of \(m\), the computation uses one loop of length \(m\), so the running time is \(O(m)\) and the extra space usage is \(O(1)\).
For the actual Project Euler range \(m=2\) to \(15\), the total work is
$$O\left(\sum_{m=2}^{15} m\right),$$
which is effectively constant in practice. If the same method were generalized to all \(m\) from 2 through \(N\), the total time would be \(O(N^2)\) with the same \(O(1)\) extra space.
Für jede ganze Zahl \(m\) von 2 bis 15 sei
$$P_m=\max \left\{x_1^1x_2^2\cdots x_m^m : x_1+x_2+\cdots+x_m=m,\ x_i \gt 0\right\}.$$
Die Exponenten \(1,2,\dots,m\) machen die Variablen bewusst unsymmetrisch: Eine Änderung bei großem Index wirkt sich viel stärker auf das Produkt aus als dieselbe Änderung bei kleinem Index. Gesucht ist also für jedes \(m\) die optimale Verteilung der Summe \(m\), danach \(\lfloor P_m\rfloor\), und schließlich die Summe dieser ganzzahligen Teile.
Auf den ersten Blick ist das eine kontinuierliche Optimierungsaufgabe in vielen Variablen. Tatsächlich ist die Struktur aber sehr starr: Der Maximierer muss proportional zum Gewichtsvektor \((1,2,\dots,m)\) sein. Damit reduziert sich das ganze Problem auf eine einzige geschlossene Formel.
Da der Logarithmus streng monoton wächst, ist das Maximieren von \(P_m\) äquivalent zum Maximieren von
$$F(x_1,\dots,x_m)=\log P_m=\sum_{i=1}^{m} i\log x_i$$
unter derselben Nebenbedingung \(x_1+\cdots+x_m=m\).
Diese Umformulierung ist aus zwei Gründen ideal. Erstens wird aus einem Produkt eine Summe, also wird Differenzieren einfach. Zweitens ist die Hesse-Matrix diagonal:
$$\frac{\partial^2 F}{\partial x_i^2}=-\frac{i}{x_i^2},\qquad \frac{\partial^2 F}{\partial x_i\partial x_j}=0 \quad (i\ne j).$$
Alle Diagonaleinträge sind im zulässigen Bereich \(x_i \gt 0\) negativ, also ist \(F\) streng konkav. Damit ist jeder innere kritische Punkt automatisch das eindeutige globale Maximum. Auch der Rand kann nicht optimal sein, denn wenn ein \(x_i\to 0^+\) geht, dann gilt \(i\log x_i\to -\infty\).
Führe einen Lagrange-Multiplikator \(\lambda\) für die lineare Nebenbedingung ein und betrachte
$$\mathcal{L}(x_1,\dots,x_m,\lambda)=\sum_{i=1}^{m} i\log x_i-\lambda\left(\sum_{i=1}^{m}x_i-m\right).$$
Die Ableitung nach jedem \(x_i\) liefert
$$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{i}{x_i}-\lambda=0,$$
also muss für jede optimale Koordinate gelten
$$x_i=\frac{i}{\lambda}.$$
Das ist die entscheidende strukturelle Aussage: Die optimalen Werte sind nicht frei verteilt, sondern wachsen linear mit dem Exponenten. Die Variable mit Gewicht \(i\) erhält genau \(i\)-mal so viel Anteil wie die Variable mit Gewicht 1.
Nun setzen wir die Nebenbedingung ein:
$$\sum_{i=1}^{m}x_i=\frac{1}{\lambda}\sum_{i=1}^{m}i=\frac{1}{\lambda}\cdot\frac{m(m+1)}{2}=m.$$
Daraus folgt
$$\lambda=\frac{m+1}{2},\qquad x_i^*=\frac{2i}{m+1}\quad (1\le i\le m).$$
Setzt man die optimalen Koordinaten in das Produkt ein, erhält man
$$P_m=\prod_{i=1}^{m}\left(\frac{2i}{m+1}\right)^i.$$
Man kann den gemeinsamen Nenner auch separat schreiben:
$$P_m=\frac{2^{1+2+\cdots+m}\prod_{i=1}^{m} i^i}{(m+1)^{1+2+\cdots+m}}=\frac{2^{m(m+1)/2}\prod_{i=1}^{m} i^i}{(m+1)^{m(m+1)/2}}.$$
Die Implementierungen multiplizieren diese Formel nicht direkt aus. Stattdessen verwenden sie die numerisch stabilere Identität
$$\log P_m=\sum_{i=1}^{m} i\log\left(\frac{2i}{m+1}\right),$$
und wenden die Exponentialfunktion erst ganz am Ende an.
Für \(m=10\) ist der Maximierer
$$\left(\frac{2}{11},\frac{4}{11},\frac{6}{11},\dots,\frac{20}{11}\right).$$
Das maximale Produkt ist also
$$P_{10}=\prod_{i=1}^{10}\left(\frac{2i}{11}\right)^i.$$
Wertet man die logarithmische Form aus, erhält man einen Wert mit ganzzahligem Anteil
$$\lfloor P_{10}\rfloor=4112.$$
Das ist ein nützlicher Kontrollpunkt, weil er sowohl die Herleitung als auch das Rundungsverhalten der Gleitkommaauswertung überprüft.
Die C++-, Python- und Java-Implementierungen verwenden direkt den geschlossenen Ausdruck für den Optimierer und führen keine numerische Suche aus. Für jedes \(m\) laufen sie über \(i=1,2,\dots,m\), berechnen die optimale Koordinate \(x_i=\frac{2i}{m+1}\) und addieren den logarithmischen Beitrag \(i\log x_i\). Nach dieser Schleife rekonstruiert eine einzige Exponentialfunktion den Wert \(P_m\).
Genau diese Auswertung im Logarithmusraum ist die zentrale numerische Idee. Das direkte Produkt enthält viele Potenzen und wäre deutlich empfindlicher gegenüber Rundungsfehlern, während die Logarithmensumme in einem moderaten Zahlenbereich bleibt und die mathematisch exakte Optimierungsformel bewahrt.
Nachdem \(P_m\) numerisch zurückgewonnen wurde, nimmt die Implementierung den ganzzahligen Anteil. Vor der Umwandlung in eine Ganzzahl wird eine winzige positive Korrektur wie \(10^{-12}\) addiert, damit Werte, die eigentlich auf einem Integer liegen, aber als etwa \(4111.999999999999\) gespeichert werden, nicht fälschlich zu klein abgeschnitten werden.
Die Endsumme entsteht, indem dieser Ablauf für \(m=2,3,\dots,15\) wiederholt und alles addiert wird. Eine der Implementierungen prüft zusätzlich den bekannten Zwischenwert \(\lfloor P_{10}\rfloor=4112\), bevor sie die vollständige Summe berechnet.
Für ein einzelnes \(m\) besteht die Rechnung aus genau einer Schleife der Länge \(m\). Daher beträgt die Laufzeit \(O(m)\) und der zusätzliche Speicherbedarf \(O(1)\).
Für den tatsächlichen Bereich der Aufgabe, also \(m=2\) bis \(15\), ist der Gesamtaufwand
$$O\left(\sum_{m=2}^{15} m\right),$$
also praktisch konstant. Verallgemeinert man dieselbe Methode auf alle \(m\) von 2 bis \(N\), so ergibt sich insgesamt \(O(N^2)\) Zeit bei unverändert \(O(1)\) zusätzlichem Speicher.
2 ile 15 arasındaki her tamsayı \(m\) için
$$P_m=\max \left\{x_1^1x_2^2\cdots x_m^m : x_1+x_2+\cdots+x_m=m,\ x_i \gt 0\right\}$$
tanımlanır. Buradaki üsler \(1,2,\dots,m\) olduğu için değişkenler simetrik değildir; büyük indisli değişkenlerdeki artış, ürünü çok daha güçlü etkiler. Amaç her \(m\) için maksimumu veren dağılımı bulmak, sonra \(\lfloor P_m\rfloor\) değerini almak ve bu tam kısımları toplamaktır.
İlk bakışta bu, çok değişkenli bir sürekli optimizasyon problemi gibi görünür. Fakat yapı son derece katıdır: maksimum noktası zorunlu olarak \((1,2,\dots,m)\) ağırlık vektörü ile orantılıdır. Bu gözlem bütün problemi tek bir kapalı forma indirir.
\(\log\) fonksiyonu sıkı artan olduğu için \(P_m\)'yi maksimize etmek ile
$$F(x_1,\dots,x_m)=\log P_m=\sum_{i=1}^{m} i\log x_i$$
ifadesini, aynı \(x_1+\cdots+x_m=m\) kısıtı altında maksimize etmek eşdeğerdir.
Bu dönüşüm iki nedenle doğrudur. Birincisi, çarpım toplam haline gelir ve türev almak kolaylaşır. İkincisi, Hessian matrisi köşegendir:
$$\frac{\partial^2 F}{\partial x_i^2}=-\frac{i}{x_i^2},\qquad \frac{\partial^2 F}{\partial x_i\partial x_j}=0 \quad (i\ne j).$$
Uygun bölgede \(x_i \gt 0\) iken bütün köşegen terimleri negatiftir; dolayısıyla \(F\) sıkı konkavdır. Bu da, içeride bulunan herhangi bir kritik noktanın otomatik olarak tek küresel maksimum olduğu anlamına gelir. Sınır da maksimum olamaz; çünkü bir \(x_i\to 0^+\) olduğunda \(i\log x_i\to -\infty\) olur.
Doğrusal kısıt için bir Lagrange çarpanı \(\lambda\) ekleyelim:
$$\mathcal{L}(x_1,\dots,x_m,\lambda)=\sum_{i=1}^{m} i\log x_i-\lambda\left(\sum_{i=1}^{m}x_i-m\right).$$
Her \(x_i\) için türev alınca
$$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{i}{x_i}-\lambda=0$$
elde edilir; yani optimum noktada
$$x_i=\frac{i}{\lambda}.$$
Asıl yapısal sonuç budur: en iyi dağılım serbest değildir, üslerle doğrusal biçimde büyümek zorundadır. Ağırlığı \(i\) olan değişken, ağırlığı 1 olan değişkenin tam \(i\) katı kadar pay alır.
Şimdi toplam kısıtını kullanalım:
$$\sum_{i=1}^{m}x_i=\frac{1}{\lambda}\sum_{i=1}^{m}i=\frac{1}{\lambda}\cdot\frac{m(m+1)}{2}=m.$$
Buradan
$$\lambda=\frac{m+1}{2},\qquad x_i^*=\frac{2i}{m+1}\quad (1\le i\le m)$$
sonucu çıkar.
Bu değerleri ürüne geri koyunca
$$P_m=\prod_{i=1}^{m}\left(\frac{2i}{m+1}\right)^i$$
elde edilir. Ortak paydayı ayırarak aynı ifadeyi
$$P_m=\frac{2^{1+2+\cdots+m}\prod_{i=1}^{m} i^i}{(m+1)^{1+2+\cdots+m}}=\frac{2^{m(m+1)/2}\prod_{i=1}^{m} i^i}{(m+1)^{m(m+1)/2}}$$
şeklinde de yazabiliriz. Uygulamalar bu çarpımı doğrudan kurmaz; bunun yerine daha güvenli olan
$$\log P_m=\sum_{i=1}^{m} i\log\left(\frac{2i}{m+1}\right)$$
toplamını hesaplayıp sonda tek bir üs alma işlemi uygular.
\(m=10\) için maksimum noktası
$$\left(\frac{2}{11},\frac{4}{11},\frac{6}{11},\dots,\frac{20}{11}\right)$$
olur. Buna karşılık maksimum ürün
$$P_{10}=\prod_{i=1}^{10}\left(\frac{2i}{11}\right)^i$$
şeklindedir. Logaritmik form sayısal olarak değerlendirildiğinde tam kısmın
$$\lfloor P_{10}\rfloor=4112$$
olduğu görülür. Bu değer, hem türetilen formülü hem de kayan nokta yuvarlama davranışını test eden iyi bir ara kontroldür.
C++, Python ve Java uygulamalarının hepsi yukarıdaki kapalı formu doğrudan kullanır; sayısal arama yapmaz. Her \(m\) için \(i=1,2,\dots,m\) üzerinden geçilir, optimal koordinat \(x_i=\frac{2i}{m+1}\) hesaplanır ve \(i\log x_i\) katkısı bir toplamda biriktirilir. Döngü bittiğinde tek bir üstel alma işlemi ile \(P_m\) geri elde edilir.
Asıl sayısal fikir log uzayında çalışmaktır. Doğrudan çarpım, çok sayıda kuvvet içerdiği için hem daha hantaldır hem de yuvarlama açısından daha kırılgandır. Logaritmaların toplamı ise ara değerleri makul ölçekte tutar ve matematiksel olarak türetilen maksimum formülü aynen korur.
\(P_m\) yaklaşık olarak hesaplandıktan sonra taban değeri alınır. Kayan nokta hataları yüzünden tam sayı olması gereken bir değer bazen \(4111.999999999999\) gibi saklanabileceği için, tamsayıya çevirmeden önce \(10^{-12}\) gibi çok küçük pozitif bir güvenlik payı eklenir.
Son cevap, bu hesabı \(m=2,3,\dots,15\) için tekrar edip sonuçları toplayarak elde edilir. Uygulamalardan biri, tam toplama geçmeden önce bilinen ara değer \(\lfloor P_{10}\rfloor=4112\) ile de kısa bir doğrulama yapar.
Tek bir \(m\) değeri için işlem, uzunluğu \(m\) olan tek bir döngüden ibarettir. Bu yüzden zaman karmaşıklığı \(O(m)\), ek bellek kullanımı ise \(O(1)\)'dir.
Asıl Project Euler aralığı olan \(m=2\) ile \(15\) için toplam maliyet
$$O\left(\sum_{m=2}^{15} m\right)$$
olur; pratikte bu sabit zamandır. Aynı yöntem 2'den \(N\)'e kadar genellenirse toplam süre \(O(N^2)\), ek bellek ise yine \(O(1)\) kalır.
Para cada entero \(m\) entre 2 y 15, se define
$$P_m=\max \left\{x_1^1x_2^2\cdots x_m^m : x_1+x_2+\cdots+x_m=m,\ x_i \gt 0\right\}.$$
Los exponentes \(1,2,\dots,m\) hacen que las variables no sean simétricas: aumentar una variable de índice grande cambia el producto mucho más que aumentar una variable de índice pequeño. La tarea consiste en encontrar la configuración óptima para cada \(m\), tomar \(\lfloor P_m\rfloor\) y sumar esas partes enteras.
A primera vista parece un problema de optimización continua con muchas variables. Sin embargo, la estructura es muy rígida: el punto que maximiza está forzado a ser proporcional al vector de pesos \((1,2,\dots,m)\). Una vez visto eso, todo el problema se reduce a una fórmula cerrada.
Como el logaritmo es estrictamente creciente, maximizar \(P_m\) es equivalente a maximizar
$$F(x_1,\dots,x_m)=\log P_m=\sum_{i=1}^{m} i\log x_i$$
bajo la misma restricción lineal \(x_1+\cdots+x_m=m\).
Esta reformulación es la correcta por dos motivos. Primero, convierte un producto en una suma y por tanto facilita la derivación. Segundo, la matriz hessiana es diagonal:
$$\frac{\partial^2 F}{\partial x_i^2}=-\frac{i}{x_i^2},\qquad \frac{\partial^2 F}{\partial x_i\partial x_j}=0 \quad (i\ne j).$$
Todas las entradas diagonales son negativas en la región factible \(x_i \gt 0\), así que \(F\) es estrictamente cóncava. Por ello, cualquier punto crítico interior es automáticamente el único máximo global. El borde tampoco puede maximizar el producto, porque si algún \(x_i\to 0^+\), entonces \(i\log x_i\to -\infty\).
Introducimos un multiplicador de Lagrange \(\lambda\) para la restricción y estudiamos
$$\mathcal{L}(x_1,\dots,x_m,\lambda)=\sum_{i=1}^{m} i\log x_i-\lambda\left(\sum_{i=1}^{m}x_i-m\right).$$
Derivando con respecto a cada \(x_i\) se obtiene
$$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{i}{x_i}-\lambda=0,$$
de modo que toda coordenada óptima debe satisfacer
$$x_i=\frac{i}{\lambda}.$$
Este es el hecho estructural clave: los valores óptimos no son arbitrarios, sino que crecen linealmente con el exponente. La variable con peso \(i\) recibe exactamente \(i\) veces la cantidad asignada a la variable con peso 1.
Ahora imponemos la restricción:
$$\sum_{i=1}^{m}x_i=\frac{1}{\lambda}\sum_{i=1}^{m}i=\frac{1}{\lambda}\cdot\frac{m(m+1)}{2}=m.$$
Por tanto,
$$\lambda=\frac{m+1}{2},\qquad x_i^*=\frac{2i}{m+1}\quad (1\le i\le m).$$
Al sustituir estas coordenadas en el producto obtenemos
$$P_m=\prod_{i=1}^{m}\left(\frac{2i}{m+1}\right)^i.$$
También puede escribirse separando el denominador común:
$$P_m=\frac{2^{1+2+\cdots+m}\prod_{i=1}^{m} i^i}{(m+1)^{1+2+\cdots+m}}=\frac{2^{m(m+1)/2}\prod_{i=1}^{m} i^i}{(m+1)^{m(m+1)/2}}.$$
Las implementaciones no multiplican esta expresión directamente. En su lugar utilizan la identidad, mucho más estable numéricamente,
$$\log P_m=\sum_{i=1}^{m} i\log\left(\frac{2i}{m+1}\right),$$
y aplican la exponencial una sola vez al final.
Para \(m=10\), el punto óptimo es
$$\left(\frac{2}{11},\frac{4}{11},\frac{6}{11},\dots,\frac{20}{11}\right).$$
Entonces el producto máximo es
$$P_{10}=\prod_{i=1}^{10}\left(\frac{2i}{11}\right)^i.$$
Al evaluar la forma logarítmica, la parte entera resulta ser
$$\lfloor P_{10}\rfloor=4112.$$
Este valor es un buen punto de control porque valida tanto la derivación matemática como el tratamiento del redondeo en coma flotante.
Las implementaciones en C++, Python y Java usan directamente el optimizador en forma cerrada y no hacen ninguna búsqueda numérica. Para cada \(m\), recorren \(i=1,2,\dots,m\), calculan la coordenada óptima \(x_i=\frac{2i}{m+1}\) y acumulan el término logarítmico \(i\log x_i\). Después de ese bucle, una sola exponencial reconstruye \(P_m\).
Esa evaluación en el dominio logarítmico es la decisión numérica central. El producto directo contiene muchas potencias y es más frágil frente a errores de redondeo, mientras que la suma de logaritmos mantiene los valores intermedios en un rango manejable y respeta exactamente la fórmula deducida.
Una vez reconstruido \(P_m\), la implementación toma su parte entera inferior. Antes de convertir a entero se añade una pequeña corrección positiva, como \(10^{-12}\), para evitar que un valor que debería ser entero, pero que se almacena como \(4111.999999999999\), se trunque por debajo del resultado correcto.
La respuesta final se obtiene repitiendo este proceso para \(m=2,3,\dots,15\) y sumando todas las partes enteras. Una de las implementaciones también verifica antes el valor intermedio conocido \(\lfloor P_{10}\rfloor=4112\).
Para un solo valor de \(m\), el cálculo usa un único bucle de longitud \(m\). Por eso, el coste temporal es \(O(m)\) y la memoria extra es \(O(1)\).
Para el rango real del problema, \(m=2\) hasta \(15\), el trabajo total es
$$O\left(\sum_{m=2}^{15} m\right),$$
lo cual es esencialmente constante en la práctica. Si el mismo método se generalizara a todos los \(m\) desde 2 hasta \(N\), el tiempo total sería \(O(N^2)\) con el mismo \(O(1)\) de memoria adicional.
对每个整数 \(m=2,3,\dots,15\)，定义
$$P_m=\max \left\{x_1^1x_2^2\cdots x_m^m : x_1+x_2+\cdots+x_m=m,\ x_i \gt 0\right\}.$$
这里的指数是 \(1,2,\dots,m\)，所以各个变量并不对称。把同样大小的一部分总和分配给 \(x_m\)，对乘积的影响远大于分配给 \(x_1\)。题目要求先求出每个 \(m\) 的最优分配，再取 \(\lfloor P_m\rfloor\)，最后把这些整数部分相加。
表面上看，这是一个多变量的连续优化问题；实际上它的结构非常刚性。最优点必然与权重向量 \((1,2,\dots,m)\) 成正比。一旦这个结论建立起来，整个问题就会收缩成一个显式公式，而不需要任何数值搜索。
因为对数函数严格递增，所以最大化 \(P_m\) 与最大化
$$F(x_1,\dots,x_m)=\log P_m=\sum_{i=1}^{m} i\log x_i$$
完全等价，而且约束仍然是同一个线性条件 \(x_1+\cdots+x_m=m\)。
这个改写有两个关键好处。第一，乘积变成求和，求导会简单得多。第二，\(F\) 的 Hessian 矩阵是对角的：
$$\frac{\partial^2 F}{\partial x_i^2}=-\frac{i}{x_i^2},\qquad \frac{\partial^2 F}{\partial x_i\partial x_j}=0 \quad (i\ne j).$$
在可行域 \(x_i \gt 0\) 内，每个对角元都严格为负，因此 \(F\) 是严格凹函数。严格凹性意味着：只要找到一个内部驻点，它就自动是唯一的全局最大值。边界也不可能给出最大值，因为如果某个 \(x_i\to 0^+\)，那么对应项 \(i\log x_i\to -\infty\)。
对线性约束引入拉格朗日乘子 \(\lambda\)，考虑
$$\mathcal{L}(x_1,\dots,x_m,\lambda)=\sum_{i=1}^{m} i\log x_i-\lambda\left(\sum_{i=1}^{m}x_i-m\right).$$
对每个 \(x_i\) 求偏导，得到
$$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{i}{x_i}-\lambda=0,$$
于是最优解必须满足
$$x_i=\frac{i}{\lambda}.$$
这一步揭示了真正的结构：最优分配不是某种复杂的非线性模式，而是简单的线性比例。权重为 \(i\) 的变量，恰好得到权重为 1 的变量的 \(i\) 倍份额。
接下来利用总和约束：
$$\sum_{i=1}^{m}x_i=\frac{1}{\lambda}\sum_{i=1}^{m}i=\frac{1}{\lambda}\cdot\frac{m(m+1)}{2}=m.$$
因此
$$\lambda=\frac{m+1}{2},\qquad x_i^*=\frac{2i}{m+1}\quad (1\le i\le m).$$
也就是说，最优点就是把总量 \(m\) 按照比例 \(1:2:\cdots:m\) 分配出去。
把最优坐标代回原式，立刻得到
$$P_m=\prod_{i=1}^{m}\left(\frac{2i}{m+1}\right)^i.$$
如果把公用分母单独提出来，也可以写成
$$P_m=\frac{2^{1+2+\cdots+m}\prod_{i=1}^{m} i^i}{(m+1)^{1+2+\cdots+m}}=\frac{2^{m(m+1)/2}\prod_{i=1}^{m} i^i}{(m+1)^{m(m+1)/2}}.$$
从数学上看，这已经是完整答案了。但实现时并不会直接把这么多幂次逐项相乘，因为那样更容易累积浮点误差。代码采用的是等价的对数形式
$$\log P_m=\sum_{i=1}^{m} i\log\left(\frac{2i}{m+1}\right),$$
先把这串和算出来，最后只做一次指数运算。
当 \(m=10\) 时，最优点是
$$\left(\frac{2}{11},\frac{4}{11},\frac{6}{11},\dots,\frac{20}{11}\right).$$
于是最大乘积为
$$P_{10}=\prod_{i=1}^{10}\left(\frac{2i}{11}\right)^i.$$
如果按对数形式数值计算，再取整数部分，就会得到
$$\lfloor P_{10}\rfloor=4112.$$
这个中间值很有用，因为它既能验证推导出的最优公式，也能检验浮点实现中的取整处理是否稳定。
C++、Python 和 Java 实现都没有去做迭代搜索或优化器求解，而是直接使用上面推导出的闭式最优解。对每个 \(m\)，程序都遍历 \(i=1,2,\dots,m\)，计算最优坐标 \(x_i=\frac{2i}{m+1}\)，然后把对应的对数贡献 \(i\log x_i\) 加到累计和里。循环结束后，再做一次指数运算恢复 \(P_m\)。
在对数域中计算，是整个实现最核心的数值策略。原始表达式是许多幂的连乘，直接相乘既不优雅，也更容易受到舍入影响；而对数求和把中间量控制在温和的范围内，同时完全保留了数学推导得到的精确结构。
恢复出 \(P_m\) 的近似值后，代码需要取下整。为了避免浮点舍入把本应接近整数的结果存成类似 \(4111.999999999999\) 这样的数，实现在转成整数之前会先加上一个很小的正数，例如 \(10^{-12}\)。这样可以防止错误地下取整到前一个整数。
最终答案就是把这个过程对 \(m=2,3,\dots,15\) 全部执行一遍，并把所有 \(\lfloor P_m\rfloor\) 相加。其中有一个实现还会先检查已知的中间结果 \(\lfloor P_{10}\rfloor=4112\)，作为一个很紧凑的正确性验证。
对于单个 \(m\)，计算只需要一个长度为 \(m\) 的循环，因此时间复杂度是 \(O(m)\)，额外空间复杂度是 \(O(1)\)。
对于题目真正需要的范围 \(m=2\) 到 \(15\)，总工作量为
$$O\left(\sum_{m=2}^{15} m\right),$$
在实际规模下几乎可以视为常数。如果把同样的方法推广到 \(m=2,3,\dots,N\)，那么总时间复杂度就是 \(O(N^2)\)，额外空间仍然保持在 \(O(1)\)。
Для каждого целого \(m\) от 2 до 15 определяется величина
$$P_m=\max \left\{x_1^1x_2^2\cdots x_m^m : x_1+x_2+\cdots+x_m=m,\ x_i \gt 0\right\}.$$
Показатели \(1,2,\dots,m\) делают переменные несимметричными: увеличение переменной с большим индексом влияет на произведение гораздо сильнее, чем такое же увеличение переменной с малым индексом. Нужно найти оптимальную конфигурацию для каждого \(m\), затем взять \(\lfloor P_m\rfloor\) и сложить эти целые части.
На первый взгляд это многомерная задача непрерывной оптимизации. На деле структура у нее очень жесткая: точка максимума обязана быть пропорциональна вектору весов \((1,2,\dots,m)\). После этого вся задача сводится к короткой явной формуле.
Так как логарифм строго возрастает, максимизация \(P_m\) эквивалентна максимизации
$$F(x_1,\dots,x_m)=\log P_m=\sum_{i=1}^{m} i\log x_i$$
при том же линейном ограничении \(x_1+\cdots+x_m=m\).
Эта замена полезна по двум причинам. Во-первых, произведение превращается в сумму, и дифференцировать становится легко. Во-вторых, матрица Гессе диагональна:
$$\frac{\partial^2 F}{\partial x_i^2}=-\frac{i}{x_i^2},\qquad \frac{\partial^2 F}{\partial x_i\partial x_j}=0 \quad (i\ne j).$$
Все диагональные элементы отрицательны в допустимой области \(x_i \gt 0\), значит \(F\) является строго вогнутой функцией. Следовательно, любая внутренняя стационарная точка автоматически является единственным глобальным максимумом. Граница тоже не может давать максимум: если некоторое \(x_i\to 0^+\), то \(i\log x_i\to -\infty\).
Введем множитель Лагранжа \(\lambda\) для ограничения и рассмотрим
$$\mathcal{L}(x_1,\dots,x_m,\lambda)=\sum_{i=1}^{m} i\log x_i-\lambda\left(\sum_{i=1}^{m}x_i-m\right).$$
Дифференцирование по каждому \(x_i\) дает
$$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{i}{x_i}-\lambda=0,$$
откуда следует, что в оптимуме
$$x_i=\frac{i}{\lambda}.$$
Это и есть главный структурный факт: оптимальные координаты не выбираются независимо, а растут линейно вместе с показателем степени. Переменная с весом \(i\) получает ровно в \(i\) раз больше, чем переменная с весом 1.
Теперь подставим условие на сумму:
$$\sum_{i=1}^{m}x_i=\frac{1}{\lambda}\sum_{i=1}^{m}i=\frac{1}{\lambda}\cdot\frac{m(m+1)}{2}=m.$$
Следовательно,
$$\lambda=\frac{m+1}{2},\qquad x_i^*=\frac{2i}{m+1}\quad (1\le i\le m).$$
Подставляя найденные координаты обратно, получаем
$$P_m=\prod_{i=1}^{m}\left(\frac{2i}{m+1}\right)^i.$$
Эту же формулу удобно переписать, выделив общий знаменатель:
$$P_m=\frac{2^{1+2+\cdots+m}\prod_{i=1}^{m} i^i}{(m+1)^{1+2+\cdots+m}}=\frac{2^{m(m+1)/2}\prod_{i=1}^{m} i^i}{(m+1)^{m(m+1)/2}}.$$
В реализациях произведение не считается напрямую. Вместо этого используется более устойчивая с численной точки зрения запись
$$\log P_m=\sum_{i=1}^{m} i\log\left(\frac{2i}{m+1}\right),$$
а экспонента применяется только один раз в конце.
Для \(m=10\) точка максимума имеет вид
$$\left(\frac{2}{11},\frac{4}{11},\frac{6}{11},\dots,\frac{20}{11}\right).$$
Максимальное произведение тогда равно
$$P_{10}=\prod_{i=1}^{10}\left(\frac{2i}{11}\right)^i.$$
Если вычислить логарифмическую форму численно и взять целую часть, получится
$$\lfloor P_{10}\rfloor=4112.$$
Это удобная контрольная точка: она проверяет и вывод формулы, и корректность округления в вычислениях с плавающей запятой.
Реализации на C++, Python и Java не запускают никакой поиск по допустимой области, а сразу используют найденный аналитический максимум. Для каждого \(m\) они проходят цикл по \(i=1,2,\dots,m\), вычисляют оптимальную координату \(x_i=\frac{2i}{m+1}\) и накапливают вклад \(i\log x_i\). После завершения цикла одна экспонента восстанавливает значение \(P_m\).
Вычисления в логарифмической области являются ключевым численным приемом. Исходное произведение содержит много степеней и при прямом перемножении было бы чувствительнее к ошибкам округления, тогда как сумма логарифмов держит промежуточные значения в умеренном диапазоне и точно следует аналитической формуле.
После восстановления приближенного значения \(P_m\) код берет нижнюю целую часть. Перед преобразованием к целому типу добавляется очень маленькая положительная поправка, например \(10^{-12}\), чтобы число, которое математически должно быть целым, но хранится как \(4111.999999999999\), не было ошибочно усечено вниз.
Финальный ответ получается повторением этой процедуры для \(m=2,3,\dots,15\) и суммированием всех \(\lfloor P_m\rfloor\). В одной из реализаций дополнительно проверяется известный промежуточный результат \(\lfloor P_{10}\rfloor=4112\).
Для одного значения \(m\) алгоритм выполняет единственный цикл длины \(m\). Поэтому время работы равно \(O(m)\), а дополнительная память равна \(O(1)\).
Для реального диапазона задачи, то есть \(m=2,\dots,15\), суммарная стоимость равна
$$O\left(\sum_{m=2}^{15} m\right),$$
что на практике является константой. Если обобщить тот же метод на все \(m\) от 2 до \(N\), получится суммарное время \(O(N^2)\) при том же \(O(1)\) дополнительной памяти.
لكل عدد صحيح \(m\) من 2 إلى 15 نعرّف
$$P_m=\max \left\{x_1^1x_2^2\cdots x_m^m : x_1+x_2+\cdots+x_m=m,\ x_i \gt 0\right\}.$$
الأسس \(1,2,\dots,m\) تجعل المتغيرات غير متناظرة؛ فزيادة المتغير ذي الفهرس الكبير تؤثر في حاصل الضرب أكثر بكثير من الزيادة نفسها عند فهرس صغير. المطلوب هو إيجاد التوزيع الأمثل لكل \(m\)، ثم أخذ \(\lfloor P_m\rfloor\)، ثم جمع هذه القيم الصحيحة.
ظاهريًا تبدو المسألة تحسينًا مستمرًا بعدة متغيرات، لكن بنيتها مقيدة جدًا. نقطة التعظيم يجب أن تكون متناسبة مع متجه الأوزان \((1,2,\dots,m)\). وبمجرد إثبات ذلك، تتحول المسألة كلها إلى صيغة مغلقة بسيطة.
لأن دالة اللوغاريتم تزايدية تمامًا، فإن تعظيم \(P_m\) يكافئ تعظيم
$$F(x_1,\dots,x_m)=\log P_m=\sum_{i=1}^{m} i\log x_i$$
تحت القيد نفسه \(x_1+\cdots+x_m=m\).
هذا التحويل مهم لسببين. أولًا، حاصل الضرب يتحول إلى مجموع، فيصبح الاشتقاق مباشرًا. ثانيًا، مصفوفة هسيان قطرية:
$$\frac{\partial^2 F}{\partial x_i^2}=-\frac{i}{x_i^2},\qquad \frac{\partial^2 F}{\partial x_i\partial x_j}=0 \quad (i\ne j).$$
كل عنصر قطري سالب داخل المجال المسموح \(x_i \gt 0\)، ولذلك تكون \(F\) دالة مقعرة بشدة. ونتيجة ذلك أن أي نقطة حرجة داخلية هي تلقائيًا القيمة العظمى العالمية الوحيدة. أما الحدود فلا يمكن أن تعطي أقصى قيمة، لأن اقتراب أحد المتغيرات من الصفر يجعل \(i\log x_i\to -\infty\).
نضيف مضاعف لاغرانج \(\lambda\) للقيد الخطي وننظر إلى
$$\mathcal{L}(x_1,\dots,x_m,\lambda)=\sum_{i=1}^{m} i\log x_i-\lambda\left(\sum_{i=1}^{m}x_i-m\right).$$
باشتقاق هذه الدالة بالنسبة إلى كل \(x_i\) نحصل على
$$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{i}{x_i}-\lambda=0,$$
ومن ثم يجب أن يحقق الحل الأمثل
$$x_i=\frac{i}{\lambda}.$$
هذه هي الحقيقة البنيوية الحاسمة: التوزيع الأمثل ليس اعتباطيًا، بل ينمو خطيًا مع الأس. المتغير ذو الوزن \(i\) يحصل على كمية تساوي \(i\) أضعاف ما يحصل عليه المتغير ذو الوزن 1.
الآن نفرض قيد المجموع:
$$\sum_{i=1}^{m}x_i=\frac{1}{\lambda}\sum_{i=1}^{m}i=\frac{1}{\lambda}\cdot\frac{m(m+1)}{2}=m.$$
إذن
$$\lambda=\frac{m+1}{2},\qquad x_i^*=\frac{2i}{m+1}\quad (1\le i\le m).$$
بالتعويض في حاصل الضرب الأصلي نحصل على
$$P_m=\prod_{i=1}^{m}\left(\frac{2i}{m+1}\right)^i.$$
ويمكن أيضًا فصل المقام المشترك وكتابة الصيغة على الشكل
$$P_m=\frac{2^{1+2+\cdots+m}\prod_{i=1}^{m} i^i}{(m+1)^{1+2+\cdots+m}}=\frac{2^{m(m+1)/2}\prod_{i=1}^{m} i^i}{(m+1)^{m(m+1)/2}}.$$
لكن التنفيذ لا يحسب هذا الحاصل مباشرة، لأن الضرب المتكرر أقل استقرارًا عدديًا. بدلًا من ذلك تُستعمل الصيغة المكافئة
$$\log P_m=\sum_{i=1}^{m} i\log\left(\frac{2i}{m+1}\right),$$
ثم يُطبَّق الأس الطبيعي مرة واحدة في النهاية.
عندما \(m=10\) تكون نقطة التعظيم
$$\left(\frac{2}{11},\frac{4}{11},\frac{6}{11},\dots,\frac{20}{11}\right).$$
وعندئذ يصبح حاصل الضرب الأعظمي
$$P_{10}=\prod_{i=1}^{10}\left(\frac{2i}{11}\right)^i.$$
وبحساب الصيغة اللوغاريتمية عدديًا ثم أخذ الجزء الصحيح السفلي نحصل على
$$\lfloor P_{10}\rfloor=4112.$$
هذه قيمة وسيطة مفيدة لأنها تتحقق من صحة الاشتقاق الرياضي ومن سلامة أسلوب التقريب العددي في التنفيذ.
تنفيذات C++ وPython وJava لا تستخدم أي بحث عددي داخل المجال المسموح، بل تنطلق مباشرة من الصيغة المغلقة للحل الأمثل. لكل \(m\)، يمر الكود على \(i=1,2,\dots,m\)، ويحسِب \(x_i=\frac{2i}{m+1}\)، ثم يضيف المساهمة اللوغاريتمية \(i\log x_i\) إلى مجموع تراكمي. وبعد انتهاء الحلقة تُستعمل دالة الأس لاسترجاع \(P_m\).
العمل في مجال اللوغاريتمات هو الفكرة العددية الأساسية هنا. حاصل الضرب الأصلي يحتوي على قوى كثيرة، وضربها مباشرة أكثر عرضة لاضطرابات التقريب. أما جمع اللوغاريتمات فيُبقي القيم الوسيطة ضمن مجال مريح، وفي الوقت نفسه يحافظ بدقة على الصيغة التي خرجت من التحليل الرياضي.
بعد استرجاع قيمة تقريبية لـ \(P_m\)، يأخذ التنفيذ الجزء الصحيح السفلي. وقبل التحويل إلى عدد صحيح تُضاف زيادة موجبة صغيرة جدًا مثل \(10^{-12}\)، حتى لا تُقتطع قيمة كان يجب أن تكون عددًا صحيحًا ولكنها خُزنت مثل \(4111.999999999999\) إلى العدد الأصغر خطأً.
النتيجة النهائية تنتج من تكرار هذه الخطوات لكل \(m=2,3,\dots,15\) ثم جمع القيم. كما أن أحد التنفيذات يفحص مسبقًا القيمة الوسيطة المعروفة \(\lfloor P_{10}\rfloor=4112\) قبل إجراء الجمع الكامل.
بالنسبة إلى قيمة واحدة من \(m\)، لا يوجد إلا حلقة واحدة طولها \(m\)، ولذلك يكون الزمن \(O(m)\) والذاكرة الإضافية \(O(1)\).
أما في النطاق الفعلي للمسألة، أي من \(m=2\) إلى \(15\)، فإن الكلفة الكلية هي
$$O\left(\sum_{m=2}^{15} m\right),$$
وهي في التطبيق العملي ثابتة تقريبًا. وإذا عُمِّمت الطريقة نفسها إلى جميع القيم من 2 حتى \(N\)، فسيكون الزمن الكلي \(O(N^2)\) مع بقاء الذاكرة الإضافية \(O(1)\).