Problem 235 asks for the real number \(r > 1\) for which the arithmetic-geometric sequence
$$u_k=(900-3k)r^{k-1}$$
has partial sum
$$s_n(r)=\sum_{k=1}^{n}u_k,\qquad s_{5000}(r)=-600000000000.$$
The coefficient \(900-3k\) is positive for \(k\le 299\), zero at \(k=300\), and negative afterwards. The problem is therefore a balancing act: choose \(r\) so that the late negative terms, which are amplified by the geometric factor \(r^{k-1}\), pull the total down to exactly \(-6\times 10^{11}\). The required output is \(r\) rounded to 12 decimal places.
This is a one-variable root-finding problem, but the finite sum has enough structure that we can see why the solution lies only slightly above 1 and why a simple bracketing method is numerically reliable.
Separate the sum into a pure geometric part and a weighted geometric part:
$$s_n(r)=900\sum_{k=1}^{n}r^{k-1}-3\sum_{k=1}^{n}kr^{k-1}.$$
For \(r\neq 1\), the standard finite-sum identities are
$$\sum_{k=1}^{n}r^{k-1}=\frac{1-r^n}{1-r},\qquad \sum_{k=1}^{n}kr^{k-1}=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}.$$
Substituting them gives the closed form
$$s_n(r)=\frac{897-900r+(3n-897)r^n+(900-3n)r^{n+1}}{(1-r)^2}.$$
For the actual problem this becomes
$$s_{5000}(r)=\frac{897-900r+14103r^{5000}-14100r^{5001}}{(1-r)^2}.$$
This formula exposes the main geometry of the problem: when \(r\) is only a little larger than 1, the two huge tail terms \(14103r^{5000}\) and \(14100r^{5001}\) nearly cancel, and the desired root appears precisely in that narrow transition zone.
The rational form has a removable singularity at \(r=1\), but the original definition is just a finite polynomial sum, so the function itself is perfectly regular there. Evaluating the series directly at \(r=1\) gives a concrete worked example:
$$s_{5000}(1)=\sum_{k=1}^{5000}(900-3k)=900\cdot 5000-3\cdot\frac{5000\cdot 5001}{2}=-33{,}007{,}500.$$
This is far above the target \(-6\times 10^{11}\), so the solution must satisfy \(r>1\). This exact identity is also a useful checkpoint because it confirms that the summation logic is aligned with the mathematics before any floating-point search begins.
At the right endpoint, the high-power tail is overwhelmingly negative. In the closed form, the dominant contribution is
$$14103r^{5000}-14100r^{5001}=14100r^{5000}\left(\frac{14103}{14100}-r\right).$$
Once \(r\) is appreciably larger than \(14103/14100\approx 1.000212766\), this contribution is negative, and at \(r=1.2\) its magnitude is enormous. That pushes the whole sum well below \(-6\times 10^{11}\). Because \(s_{5000}(r)\) is continuous, there is at least one root inside \([1,1.2]\).
The implementations use the additional problem-specific fact that within this bracket the sum decreases through the target only once, so the interval can be shrunk safely by bisection.
Even after the closed-form reduction, the equation \(s_{5000}(r)=-600000000000\) is still a degree-4999 problem in \(r\). There is no practical symbolic shortcut for the exact root, and derivative-based methods are unnecessary because the search interval is already known. For a continuous function with a single crossing, bisection is the simplest robust choice.
The C++, Python, and Java implementations all avoid using the rational closed form during evaluation. Instead they build the series in one pass, starting with the current power equal to 1 and multiplying by \(r\) after every term. If \(P_k=r^{k-1}\), the updates are
$$P_1=1,\qquad P_{k+1}=rP_k,\qquad S_k=S_{k-1}+(900-3k)P_k.$$
After \(k\) iterations, the invariant is exact: \(S_k=s_k(r)\) and the stored power for the next step is \(r^k\). This matches the mathematical definition term for term and avoids the cancellation that can occur if one substitutes into the \((1-r)^2\) formula very close to \(r=1\).
Each evaluation of \(s_{5000}(r)\) touches the 5000 terms once, so the numerical core is only repeated multiplication and addition. There is no table of powers and no recursion depth to manage; the sum is streamed from left to right.
The solver starts with a lower endpoint at 1 and an upper endpoint at 1.2. At each iteration it evaluates the midpoint. If the midpoint sum is still above the target, the root must be further right, so the lower endpoint moves up; otherwise the upper endpoint moves down. The key invariant is that the left endpoint always remains on the "sum too large" side while the right endpoint remains on the "sum too small" side.
After 200 halving steps, the interval width is vastly smaller than \(10^{-12}\), so formatting the midpoint to 12 decimal places is safe. The core numerical loop is the same in all three languages; one version additionally exposes the problem parameters as optional inputs and verifies the exact \(r=1\) checkpoint before solving.
One evaluation of the series costs \(O(n)\) time and \(O(1)\) memory. With \(n=5000\) and a fixed 200 bisection steps, the full computation performs about \(5000\times 200=1{,}000{,}000\) term updates, so the practical runtime is very small.
In asymptotic form, if the number of bisection iterations is \(I\), the total cost is \(O(nI)\) time and \(O(1)\) space. Because \(I\) is fixed here, the implementation is effectively linear in \(n\).
Problem 235 verlangt die reelle Zahl \(r > 1\), für die die arithmetisch-geometrische Folge
$$u_k=(900-3k)r^{k-1}$$
die Partialsumme
$$s_n(r)=\sum_{k=1}^{n}u_k,\qquad s_{5000}(r)=-600000000000$$
besitzt. Der Faktor \(900-3k\) ist für \(k\le 299\) positiv, bei \(k=300\) gleich null und danach negativ. Gesucht ist also genau der Wert von \(r\), bei dem der durch \(r^{k-1}\) verstärkte negative Endbereich die frühen positiven Terme gerade auf \(-6\times 10^{11}\) herunterzieht. Ausgegeben werden soll \(r\) auf 12 Nachkommastellen.
Formal ist das nur eine Gleichung in einer Variablen, aber die endliche Summe hat genug Struktur, um die Lage der Lösung und die Stabilität des numerischen Verfahrens klar zu erklären.
Man zerlegt die Summe in einen geometrischen Teil und einen gewichtet-geometrischen Teil:
$$s_n(r)=900\sum_{k=1}^{n}r^{k-1}-3\sum_{k=1}^{n}kr^{k-1}.$$
Für \(r\neq 1\) gelten die Standardformeln
$$\sum_{k=1}^{n}r^{k-1}=\frac{1-r^n}{1-r},\qquad \sum_{k=1}^{n}kr^{k-1}=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}.$$
Damit erhält man die geschlossene Darstellung
$$s_n(r)=\frac{897-900r+(3n-897)r^n+(900-3n)r^{n+1}}{(1-r)^2}.$$
Für \(n=5000\) wird daraus
$$s_{5000}(r)=\frac{897-900r+14103r^{5000}-14100r^{5001}}{(1-r)^2}.$$
Daran sieht man sofort die eigentliche Geometrie des Problems: Schon für \(r\) nur wenig größer als 1 sind die beiden Endterme riesig, und die gesuchte Lösung liegt genau dort, wo diese Beiträge fast gegeneinander wegfallen.
Die rationale Form hat bei \(r=1\) nur eine hebbare Singularität; die ursprüngliche Definition ist ja eine endliche Polynomsumme und deshalb dort vollkommen regulär. Eine konkrete Probe ist
$$s_{5000}(1)=\sum_{k=1}^{5000}(900-3k)=900\cdot 5000-3\cdot\frac{5000\cdot 5001}{2}=-33{,}007{,}500.$$
Dieser Wert liegt deutlich oberhalb des Zielwerts \(-6\times 10^{11}\), also muss die gesuchte Lösung rechts von 1 liegen. Dieselbe exakte Identität eignet sich auch als Kontrollpunkt vor der eigentlichen Gleitkommasuche.
Am rechten Rand dominiert der hochpotente negative Endbereich. In der geschlossenen Form ist der wichtigste Anteil
$$14103r^{5000}-14100r^{5001}=14100r^{5000}\left(\frac{14103}{14100}-r\right).$$
Sobald \(r\) merklich größer als \(14103/14100\approx 1.000212766\) ist, wird dieser Beitrag negativ, und bei \(r=1.2\) ist seine Größenordnung gewaltig. Dadurch liegt die gesamte Summe weit unter \(-6\times 10^{11}\). Wegen der Stetigkeit von \(s_{5000}(r)\) muss also mindestens eine Nullstelle im Suchintervall liegen.
Die Implementierungen nutzen zusätzlich die problemspezifische Tatsache, dass die Summe in diesem Intervall das Ziel nur einmal schneidet. Deshalb kann die Klammer per Bisektion sicher verengt werden.
Auch nach der Umformung bleibt \(s_{5000}(r)=-600000000000\) eine Gleichung vom Grad 4999 in \(r\). Eine symbolische Auflösung ist praktisch wertlos, und Newton-Verfahren sind nicht nötig, weil das Intervall bereits bekannt ist. Für eine stetige Funktion mit genau einem Vorzeichenwechsel ist Bisektion die einfachste robuste Wahl.
Die C++-, Python- und Java-Implementierungen verwenden zur Auswertung bewusst nicht die rationale Formel. Stattdessen bauen sie die Summe in einem einzigen Durchlauf auf: Die aktuelle Potenz startet bei 1 und wird nach jedem Term mit \(r\) multipliziert. Mit \(P_k=r^{k-1}\) lauten die Updates
$$P_1=1,\qquad P_{k+1}=rP_k,\qquad S_k=S_{k-1}+(900-3k)P_k.$$
Nach \(k\) Schritten gilt exakt die Invariante \(S_k=s_k(r)\), und die gespeicherte Potenz für den nächsten Schritt ist \(r^k\). Das bildet die mathematische Definition eins zu eins ab und vermeidet die Auslöschung, die nahe bei \(r=1\) in der Darstellung mit \((1-r)^2\) auftreten kann.
Jede Berechnung von \(s_{5000}(r)\) besucht die 5000 Terme genau einmal. Der numerische Kern besteht also nur aus wiederholten Multiplikationen und Additionen. Weder eine Potenztabelle noch Rekursion sind nötig.
Der Solver startet mit der unteren Grenze 1 und der oberen Grenze 1.2. In jedem Schritt wird der Mittelpunkt ausgewertet. Liegt dessen Summe noch oberhalb des Ziels, muss die Lösung weiter rechts liegen und die untere Grenze wird angehoben; andernfalls wird die obere Grenze abgesenkt. Die entscheidende Invariante lautet: Links bleibt man stets auf der Seite "Summe zu groß", rechts stets auf der Seite "Summe zu klein".
Nach 200 Halbierungen ist die Intervallbreite weit kleiner als \(10^{-12}\), sodass die Ausgabe auf 12 Nachkommastellen sicher ist. Die numerische Kerneidee ist in allen drei Sprachen gleich; eine Version erlaubt zusätzlich optionale Problemparameter und prüft vorab den exakten Kontrollwert bei \(r=1\).
Eine Auswertung der Reihe kostet \(O(n)\) Zeit und \(O(1)\) Speicher. Mit \(n=5000\) und festen 200 Bisektionsschritten entstehen ungefähr \(5000\times 200=1{,}000{,}000\) Termaktualisierungen, also praktisch sehr wenig Arbeit.
Asymptotisch gilt bei \(I\) Bisektionsschritten insgesamt \(O(nI)\) Zeit und \(O(1)\) Speicher. Da \(I\) hier konstant ist, verhält sich die Implementierung effektiv linear in \(n\).
Problem 235,
$$u_k=(900-3k)r^{k-1}$$
aritmetik-geometrik dizisi için
$$s_n(r)=\sum_{k=1}^{n}u_k,\qquad s_{5000}(r)=-600000000000$$
eşitliğini sağlayan \(r>1\) reel sayısını ister. \(900-3k\) katsayısı \(k\le 299\) için pozitiftir, \(k=300\) noktasında sıfır olur ve sonrasında negatife döner. Dolayısıyla asıl mesele, geometrik çarpanın büyüttüğü geç dönem negatif terimlerin erken dönem pozitif kısmı tam olarak \(-6\times 10^{11}\) seviyesine indireceği \(r\) değerini bulmaktır. İstenen çıktı, \(r\)'nin 12 ondalık basamağa yuvarlanmış halidir.
Bu problem tek değişkenli bir kök bulma problemi gibi görünür, fakat sonlu toplamın yapısı çözümün neden 1'in hemen üstünde olduğunu ve neden basit bir aralık daraltma yönteminin yeterli olduğunu açıkça gösterir.
Toplamı saf geometrik kısım ile ağırlıklı geometrik kısma ayıralım:
$$s_n(r)=900\sum_{k=1}^{n}r^{k-1}-3\sum_{k=1}^{n}kr^{k-1}.$$
\(r\neq 1\) için standart sonlu toplam özdeşlikleri
$$\sum_{k=1}^{n}r^{k-1}=\frac{1-r^n}{1-r},\qquad \sum_{k=1}^{n}kr^{k-1}=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}$$
şeklindedir. Bunları yerine koyunca
$$s_n(r)=\frac{897-900r+(3n-897)r^n+(900-3n)r^{n+1}}{(1-r)^2}$$
elde edilir. Gerçek problemde bu
$$s_{5000}(r)=\frac{897-900r+14103r^{5000}-14100r^{5001}}{(1-r)^2}$$
olur. Böylece problemin geometrisi görünür hale gelir: \(r\) yalnızca biraz 1'in üstüne çıktığında bile son iki büyük terim neredeyse birbirini götürür ve aranan kök tam bu hassas geçiş bölgesinde ortaya çıkar.
Rasyonel biçimde \(r=1\) noktasında kaldırılabilir bir tekillik vardır; fakat özgün tanım sonlu bir polinom toplamı olduğu için fonksiyonun kendisi burada tamamen düzgündür. Doğrudan hesaplanan somut bir örnek şudur:
$$s_{5000}(1)=\sum_{k=1}^{5000}(900-3k)=900\cdot 5000-3\cdot\frac{5000\cdot 5001}{2}=-33{,}007{,}500.$$
Bu değer hedef olan \(-6\times 10^{11}\)'in çok üzerindedir; demek ki çözüm \(1\)'in sağındadır. Aynı eşitlik, kayan noktalı arama başlamadan önce toplam mantığının doğru kurulduğunu test etmek için de çok yararlı bir kontrol noktasıdır.
Sağ uçta yüksek kuvvetli negatif kuyruk baskın hale gelir. Kapalı biçimde öne çıkan katkı
$$14103r^{5000}-14100r^{5001}=14100r^{5000}\left(\frac{14103}{14100}-r\right)$$
ifadesidir. \(r\), \(14103/14100\approx 1.000212766\) değerinden anlamlı biçimde büyük olduğunda bu katkı negatiftir; \(r=1.2\) için ise büyüklüğü çok fazladır. Bu da toplamı \(-6\times 10^{11}\)'in oldukça altına iter. \(s_{5000}(r)\) sürekli olduğundan, \([1,1.2]\) içinde en az bir kök vardır.
Uygulamalar ayrıca bu aralıkta toplamın hedefi yalnızca bir kez kestiği problem-özel olgusundan yararlanır; böylece bisection ile aralık güvenli biçimde daraltılabilir.
Kapalı biçime geçtikten sonra bile \(s_{5000}(r)=-600000000000\) denklemi hâlâ \(r\) için 4999. dereceden bir problemdir. Sembolik çözümün pratik bir karşılığı yoktur; türev kullanan yöntemlere de gerek yoktur, çünkü aralık zaten bilinmektedir. Sürekli ve tek geçişli bir fonksiyon için bisection en sade ve en sağlam seçenektir.
C++, Python ve Java uygulamaları değerlendirme sırasında rasyonel kapalı biçimi kullanmaz. Bunun yerine toplamı tek geçişte kurarlar: mevcut kuvvet 1 ile başlar ve her terimden sonra \(r\) ile çarpılır. \(P_k=r^{k-1}\) olacak şekilde güncellemeler
$$P_1=1,\qquad P_{k+1}=rP_k,\qquad S_k=S_{k-1}+(900-3k)P_k$$
biçimindedir. \(k\) adım sonra değişmez durum tam olarak şudur: \(S_k=s_k(r)\) ve bir sonraki adım için tutulan kuvvet \(r^k\)'dir. Bu, matematiksel tanımı terim terim izler ve \(r=1\)'e çok yakınken \((1-r)^2\) içeren formülde oluşabilecek iptal sorunlarından kaçınır.
Her \(s_{5000}(r)\) değerlendirmesi 5000 terimin her birine bir kez dokunur. Sayısal çekirdek yalnızca tekrarlı çarpma ve toplamadan ibarettir; ne kuvvet tablosu gerekir ne de özyineleme derinliği yönetimi.
Çözücü alt sınırı 1, üst sınırı 1.2 alarak başlar. Her turda orta nokta hesaplanır ve toplam değerlendirilir. Orta noktadaki toplam hâlâ hedefin üzerindeyse kök daha sağdadır, dolayısıyla alt sınır yükseltilir; aksi halde üst sınır aşağı çekilir. Temel değişmez şudur: sol uç her zaman "toplam fazla büyük" tarafında, sağ uç ise her zaman "toplam fazla küçük" tarafında kalır.
200 yarılama adımından sonra aralık genişliği \(10^{-12}\)'den çok daha küçüktür; dolayısıyla orta noktayı 12 ondalık basamakla yazdırmak güvenlidir. Sayısal çekirdek üç dilde de aynıdır; sürümlerden biri ayrıca problem parametrelerini isteğe bağlı giriş olarak kabul eder ve aramadan önce \(r=1\) kontrolünü doğrular.
Serinin tek bir değerlendirmesi \(O(n)\) zaman ve \(O(1)\) bellek maliyetine sahiptir. \(n=5000\) ve sabit 200 bisection adımı ile toplam iş yaklaşık \(5000\times 200=1{,}000{,}000\) terim güncellemesidir; pratikte çalışma süresi bu yüzden çok küçüktür.
Asimptotik olarak, bisection yineleme sayısı \(I\) ise toplam maliyet \(O(nI)\) zaman ve \(O(1)\) alandır. Burada \(I\) sabit olduğu için uygulama fiilen \(n\)'de lineerdir.
El Problema 235 pide el número real \(r > 1\) para el cual la sucesión aritmético-geométrica
$$u_k=(900-3k)r^{k-1}$$
tiene suma parcial
$$s_n(r)=\sum_{k=1}^{n}u_k,\qquad s_{5000}(r)=-600000000000.$$
El coeficiente \(900-3k\) es positivo mientras \(k\le 299\), vale cero en \(k=300\) y después se vuelve negativo. Por eso el problema consiste en escoger \(r\) de modo que la cola negativa, amplificada por \(r^{k-1}\), compense exactamente la parte positiva inicial y lleve la suma hasta \(-6\times 10^{11}\). La salida debe ser \(r\) redondeado a 12 decimales.
Es un problema de búsqueda de raíces en una sola variable, pero la suma finita tiene suficiente estructura para explicar por qué la solución está apenas por encima de 1 y por qué un método de acotación es suficiente.
Separamos la suma en una parte geométrica pura y otra geométrica ponderada:
$$s_n(r)=900\sum_{k=1}^{n}r^{k-1}-3\sum_{k=1}^{n}kr^{k-1}.$$
Para \(r\neq 1\), las identidades finitas estándar son
$$\sum_{k=1}^{n}r^{k-1}=\frac{1-r^n}{1-r},\qquad \sum_{k=1}^{n}kr^{k-1}=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}.$$
Al sustituirlas obtenemos
$$s_n(r)=\frac{897-900r+(3n-897)r^n+(900-3n)r^{n+1}}{(1-r)^2}.$$
En el caso concreto del problema,
$$s_{5000}(r)=\frac{897-900r+14103r^{5000}-14100r^{5001}}{(1-r)^2}.$$
Esta expresión deja ver la geometría real del problema: cuando \(r\) es apenas mayor que 1, los dos términos gigantes del final casi se cancelan, y la raíz buscada aparece precisamente en esa zona de transición.
La forma racional tiene una singularidad removible en \(r=1\), pero la definición original es simplemente una suma finita de polinomios, así que la función es completamente regular ahí. Un ejemplo concreto es
$$s_{5000}(1)=\sum_{k=1}^{5000}(900-3k)=900\cdot 5000-3\cdot\frac{5000\cdot 5001}{2}=-33{,}007{,}500.$$
Ese valor está muy por encima del objetivo \(-6\times 10^{11}\), así que la solución tiene que estar a la derecha de 1. Esta identidad exacta también sirve como comprobación práctica antes de iniciar la búsqueda numérica.
En el extremo derecho domina la cola negativa de gran potencia. En la forma cerrada, la contribución principal es
$$14103r^{5000}-14100r^{5001}=14100r^{5000}\left(\frac{14103}{14100}-r\right).$$
En cuanto \(r\) es claramente mayor que \(14103/14100\approx 1.000212766\), esta cantidad se vuelve negativa; en \(r=1.2\) su magnitud es enorme. Eso arrastra la suma completa muy por debajo de \(-6\times 10^{11}\). Como \(s_{5000}(r)\) es continua, debe existir al menos una raíz dentro de \([1,1.2]\).
Las implementaciones aprovechan además el hecho específico de este problema de que, dentro de ese intervalo, la suma cruza el objetivo una sola vez. Por eso la bisección puede reducir el intervalo con seguridad.
Incluso después de obtener la forma cerrada, la ecuación \(s_{5000}(r)=-600000000000\) sigue siendo un problema de grado 4999 en \(r\). No hay un atajo simbólico útil para la raíz exacta, y los métodos basados en derivadas no hacen falta porque el intervalo de búsqueda ya está identificado. Para una función continua con un único cruce, la bisección es la opción más robusta.
Las implementaciones en C++, Python y Java evitan usar la forma racional durante la evaluación. En su lugar construyen la suma en una sola pasada: la potencia actual empieza en 1 y después de cada término se multiplica por \(r\). Si \(P_k=r^{k-1}\), las actualizaciones son
$$P_1=1,\qquad P_{k+1}=rP_k,\qquad S_k=S_{k-1}+(900-3k)P_k.$$
Tras \(k\) iteraciones, la invariante es exacta: \(S_k=s_k(r)\) y la potencia almacenada para el siguiente paso es \(r^k\). Esto reproduce la definición matemática término a término y evita la cancelación que puede aparecer muy cerca de \(r=1\) si se trabaja con la fórmula que divide por \((1-r)^2\).
Cada evaluación de \(s_{5000}(r)\) recorre los 5000 términos una sola vez. El núcleo numérico se reduce a multiplicaciones y sumas repetidas; no se necesita una tabla de potencias ni profundidad recursiva.
El solucionador parte de un extremo inferior igual a 1 y uno superior igual a 1.2. En cada iteración evalúa el punto medio. Si la suma en el punto medio sigue por encima del objetivo, la raíz debe estar más a la derecha y se mueve el extremo inferior; en caso contrario se baja el extremo superior. La invariante clave es que el extremo izquierdo siempre queda del lado "la suma todavía es demasiado grande" y el derecho del lado "la suma ya es demasiado pequeña".
Después de 200 pasos de halving, la anchura del intervalo es muchísimo menor que \(10^{-12}\), así que mostrar el punto medio con 12 decimales es seguro. La idea numérica central es la misma en los tres lenguajes; una versión además permite parametrizar el problema y verificar la identidad exacta en \(r=1\) antes de resolver.
Una evaluación de la serie cuesta \(O(n)\) tiempo y \(O(1)\) memoria. Con \(n=5000\) y 200 iteraciones fijas de bisección, el trabajo total es de aproximadamente \(5000\times 200=1{,}000{,}000\) actualizaciones de término, así que el tiempo real de ejecución es muy pequeño.
En forma asintótica, si el número de iteraciones de bisección es \(I\), el coste total es \(O(nI)\) tiempo y \(O(1)\) espacio. Como aquí \(I\) es constante, la implementación es efectivamente lineal en \(n\).
第 235 题要求找到一个实数 \(r > 1\)，使得算术-几何型数列
$$u_k=(900-3k)r^{k-1}$$
的部分和满足
$$s_n(r)=\sum_{k=1}^{n}u_k,\qquad s_{5000}(r)=-600000000000.$$
这里的系数 \(900-3k\) 在 \(k\le 299\) 时为正，在 \(k=300\) 时恰好为 0，在之后全部为负。也就是说，前面的若干项把总和往上推，后面大量负项再借助 \(r^{k-1}\) 的放大作用把总和往下拉。题目的核心就是找到那个恰好把总和压到 \(-6\times 10^{11}\) 的 \(r\)，并把它保留到小数点后 12 位。
表面上这是一个单变量求根问题，但这个有限和本身非常有结构。只要把结构拆开，就能看出为什么答案只比 1 大一点点，以及为什么二分法已经足够稳定。
先把总和拆成普通几何和与带权几何和两部分：
$$s_n(r)=900\sum_{k=1}^{n}r^{k-1}-3\sum_{k=1}^{n}kr^{k-1}.$$
当 \(r\neq 1\) 时，有标准恒等式
$$\sum_{k=1}^{n}r^{k-1}=\frac{1-r^n}{1-r},\qquad \sum_{k=1}^{n}kr^{k-1}=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}.$$
代入后可得
$$s_n(r)=\frac{897-900r+(3n-897)r^n+(900-3n)r^{n+1}}{(1-r)^2}.$$
对本题的 \(n=5000\) 而言，公式变成
$$s_{5000}(r)=\frac{897-900r+14103r^{5000}-14100r^{5001}}{(1-r)^2}.$$
这个形式一下子揭示了问题的关键：当 \(r\) 只比 1 稍微大一点时，末尾那两个超大的项 \(14103r^{5000}\) 与 \(14100r^{5001}\) 会几乎互相抵消，而真正的解就藏在这段极窄的过渡区间里。
上面的有理式在 \(r=1\) 处看起来有分母为 0 的问题，但这只是一个可去奇点。原始定义本来就是有限多项式求和，所以函数本身在 \(r=1\) 完全良好。直接代入 \(r=1\) 可以得到一个很有用的实际例子：
$$s_{5000}(1)=\sum_{k=1}^{5000}(900-3k)=900\cdot 5000-3\cdot\frac{5000\cdot 5001}{2}=-33{,}007{,}500.$$
这个值远高于目标 \(-6\times 10^{11}\)，因此所求解一定在 1 的右边。这个精确等式也很适合做实现层面的自检，因为它能在任何浮点搜索开始之前确认求和逻辑没有偏离数学定义。
在右端点附近，高次幂负尾部会完全占据主导地位。在闭式里，最关键的贡献是
$$14103r^{5000}-14100r^{5001}=14100r^{5000}\left(\frac{14103}{14100}-r\right).$$
一旦 \(r\) 明显大于 \(14103/14100\approx 1.000212766\)，这部分就会变成负数；到了 \(r=1.2\) 时，它的绝对值已经大得惊人，足以把整个和压到 \(-6\times 10^{11}\) 以下。由于 \(s_{5000}(r)\) 是连续函数，所以在 \([1,1.2]\) 内至少存在一个根。
实现还利用了这个题目的额外事实：在这个区间里，和函数只会穿过目标一次，因此可以放心地用二分法不断缩小区间。
即使写出了闭式，方程 \(s_{5000}(r)=-600000000000\) 本质上仍然是关于 \(r\) 的 4999 次问题。想要符号求出精确根没有现实意义，而基于导数的方法也没有必要，因为搜索区间已经知道了。对一个连续且只有一次穿越的函数来说，二分法正是最稳妥、最直接的选择。
C++、Python 和 Java 的实现都没有在数值计算时直接套用有理闭式，而是按定义逐项累加。当前幂从 1 开始，每处理一项就乘一次 \(r\)。如果记 \(P_k=r^{k-1}\)，更新关系就是
$$P_1=1,\qquad P_{k+1}=rP_k,\qquad S_k=S_{k-1}+(900-3k)P_k.$$
这样在做完第 \(k\) 步之后，有一个非常清晰的不变量：\(S_k=s_k(r)\)，而为下一步保留的幂正好是 \(r^k\)。这种写法逐项忠实复现数学定义，同时也避免了在 \(r\) 非常接近 1 时直接使用 \((1-r)^2\) 分母公式所带来的数值抵消问题。
每次评价 \(s_{5000}(r)\) 时，只需要顺序访问 5000 项各一次。数值核心就是重复的乘法和加法，不需要预先存储整张幂表，也没有递归栈或复杂状态。
求解器把左端点设为 1，右端点设为 1.2。每一轮都取中点并计算对应的总和。如果中点的总和仍然高于目标值，说明根还在右边，于是左端点右移；否则右端点左移。整个过程中最重要的不变量是：左端点始终位于“总和偏大”的一侧，右端点始终位于“总和偏小”的一侧。
经过 200 次对半收缩后，区间宽度会远小于 \(10^{-12}\)，因此把中点格式化到小数点后 12 位是安全的。三种语言的核心数值流程完全一致；其中一个版本还支持把题目的参数作为可选输入，并在正式搜索前检查 \(r=1\) 时的精确恒等式。
一次级数求值的时间复杂度是 \(O(n)\)，空间复杂度是 \(O(1)\)。本题中 \(n=5000\)，二分迭代固定为 200 次，所以总共大约只做 \(5000\times 200=1{,}000{,}000\) 次项更新，实际运行成本非常低。
如果把二分迭代次数记为 \(I\)，总复杂度就是 \(O(nI)\) 时间和 \(O(1)\) 空间。由于这里的 \(I\) 是常数，所以整个实现对 \(n\) 来说实际上是线性的。
В задаче 235 нужно найти действительное число \(r > 1\), для которого арифметико-геометрическая последовательность
$$u_k=(900-3k)r^{k-1}$$
имеет частичную сумму
$$s_n(r)=\sum_{k=1}^{n}u_k,\qquad s_{5000}(r)=-600000000000.$$
Коэффициент \(900-3k\) положителен при \(k\le 299\), обращается в нуль при \(k=300\), а дальше становится отрицательным. Значит, ранние члены толкают сумму вверх, а длинный отрицательный хвост, усиленный множителем \(r^{k-1}\), тянет ее вниз. Нужно подобрать именно то \(r\), при котором итог становится равен \(-6\times 10^{11}\), и вывести ответ с точностью до 12 знаков после запятой.
Формально это задача на поиск корня одной функции, но у конечной суммы есть достаточно явная структура, чтобы понять и положение решения, и выбор численного метода.
Разобьем сумму на геометрическую часть и геометрическую часть с линейным весом:
$$s_n(r)=900\sum_{k=1}^{n}r^{k-1}-3\sum_{k=1}^{n}kr^{k-1}.$$
Для \(r\neq 1\) используются стандартные формулы
$$\sum_{k=1}^{n}r^{k-1}=\frac{1-r^n}{1-r},\qquad \sum_{k=1}^{n}kr^{k-1}=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}.$$
После подстановки получаем
$$s_n(r)=\frac{897-900r+(3n-897)r^n+(900-3n)r^{n+1}}{(1-r)^2}.$$
В нашем случае
$$s_{5000}(r)=\frac{897-900r+14103r^{5000}-14100r^{5001}}{(1-r)^2}.$$
Эта запись хорошо показывает механику задачи: когда \(r\) лишь немного больше 1, два огромных хвостовых члена почти взаимно уничтожаются, и именно в этой узкой зоне возникает искомый корень.
У рациональной формы в точке \(r=1\) есть устранимая особенность, но исходное определение представляет собой конечную полиномиальную сумму, так что сама функция там совершенно регулярна. Полезный конкретный пример:
$$s_{5000}(1)=\sum_{k=1}^{5000}(900-3k)=900\cdot 5000-3\cdot\frac{5000\cdot 5001}{2}=-33{,}007{,}500.$$
Это значение значительно выше цели \(-6\times 10^{11}\), значит решение обязательно лежит правее 1. Ту же точную формулу удобно использовать как контроль перед тем, как переходить к поиску с плавающей точкой.
На правом конце интервала доминирует отрицательный высокостепенной хвост. В замкнутой формуле главный вклад имеет вид
$$14103r^{5000}-14100r^{5001}=14100r^{5000}\left(\frac{14103}{14100}-r\right).$$
Как только \(r\) заметно больше \(14103/14100\approx 1.000212766\), этот вклад становится отрицательным; при \(r=1.2\) его модуль уже огромен. Поэтому вся сумма уходит намного ниже \(-6\times 10^{11}\). Так как \(s_{5000}(r)\) непрерывна, внутри \([1,1.2]\) обязательно есть хотя бы один корень.
Реализации используют и дополнительный факт, характерный именно для этой задачи: в данном интервале сумма пересекает целевой уровень только один раз. Поэтому метод бисекции сохраняет корректную скобку на каждом шаге.
Даже после перехода к замкнутой формуле уравнение \(s_{5000}(r)=-600000000000\) остается задачей 4999-й степени по \(r\). Полезного символического сокращения здесь нет, а методы Ньютона и подобные им не нужны, потому что подходящий интервал уже известен. Для непрерывной функции с единственным пересечением цели бисекция дает максимально надежную схему.
Реализации на C++, Python и Java при численном вычислении не подставляют рациональную формулу напрямую. Вместо этого они набирают сумму за один проход: текущая степень начинается с 1 и после каждого члена умножается на \(r\). Если обозначить \(P_k=r^{k-1}\), то обновления имеют вид
$$P_1=1,\qquad P_{k+1}=rP_k,\qquad S_k=S_{k-1}+(900-3k)P_k.$$
После \(k\) шагов точный инвариант таков: \(S_k=s_k(r)\), а сохраненная для следующего шага степень равна \(r^k\). Это буквально повторяет математическое определение и одновременно избегает потери точности, которая может возникать возле \(r=1\) при работе с формулой, делящей на \((1-r)^2\).
Каждое вычисление \(s_{5000}(r)\) просматривает все 5000 членов ровно по одному разу. Численное ядро состоит только из повторяющихся умножений и сложений; таблица степеней и рекурсия не нужны.
Решатель стартует с левой границы 1 и правой границы 1.2. На каждом шаге он берет середину интервала и вычисляет сумму. Если значение в середине все еще выше цели, корень должен лежать правее, и левая граница сдвигается вправо; иначе уменьшается правая граница. Главный инвариант таков: левая граница всегда остается на стороне "сумма слишком велика", а правая - на стороне "сумма уже слишком мала".
После 200 делений пополам ширина интервала становится намного меньше \(10^{-12}\), поэтому вывод середины с 12 знаками после запятой надежен. Центральная численная идея одинакова во всех трех языках; одна из версий дополнительно позволяет задавать параметры задачи и проверяет точное тождество при \(r=1\) перед запуском поиска.
Одно вычисление ряда требует \(O(n)\) времени и \(O(1)\) памяти. При \(n=5000\) и фиксированных 200 шагах бисекции получается примерно \(5000\times 200=1{,}000{,}000\) обновлений членов, так что практическая стоимость очень мала.
Асимптотически, если число шагов бисекции обозначить через \(I\), суммарная сложность равна \(O(nI)\) по времени и \(O(1)\) по памяти. Поскольку здесь \(I\) константно, реализация фактически линейна по \(n\).
تطلب المسألة 235 إيجاد العدد الحقيقي \(r > 1\) الذي يجعل المتتالية الحسابية الهندسية
$$u_k=(900-3k)r^{k-1}$$
تملك المجموع الجزئي
$$s_n(r)=\sum_{k=1}^{n}u_k,\qquad s_{5000}(r)=-600000000000.$$
المعامل \(900-3k\) يكون موجبًا عندما \(k\le 299\)، ويساوي الصفر عند \(k=300\)، ثم يصبح سالبًا بعد ذلك. لذلك فجوهر المسألة هو اختيار \(r\) بحيث تقوم الذيل السالبة المتأخرة، بعد أن تتضخم بعامل \(r^{k-1}\)، بموازنة الجزء الموجب في البداية وصولًا إلى القيمة الدقيقة \(-6\times 10^{11}\). والمطلوب في النهاية هو كتابة \(r\) مقربًا إلى 12 منزلة عشرية.
من الناحية الشكلية هذه مسألة إيجاد جذر لدالة في متغير واحد، لكن بنية المجموع المنتهي تكشف بوضوح لماذا يكون الحل قريبًا جدًا من 1 ولماذا تكفي طريقة تنصيف المجال.
نقسم المجموع إلى جزء هندسي خالص وجزء هندسي موزون:
$$s_n(r)=900\sum_{k=1}^{n}r^{k-1}-3\sum_{k=1}^{n}kr^{k-1}.$$
عندما \(r\neq 1\)، لدينا الهويتان القياسيتان
$$\sum_{k=1}^{n}r^{k-1}=\frac{1-r^n}{1-r},\qquad \sum_{k=1}^{n}kr^{k-1}=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}.$$
وبالتعويض نحصل على
$$s_n(r)=\frac{897-900r+(3n-897)r^n+(900-3n)r^{n+1}}{(1-r)^2}.$$
وفي هذه المسألة تحديدًا تصبح الصيغة
$$s_{5000}(r)=\frac{897-900r+14103r^{5000}-14100r^{5001}}{(1-r)^2}.$$
هذه الكتابة توضح الفكرة الحقيقية: عندما يكون \(r\) أكبر من 1 بقليل فقط، فإن الحدين الضخمين في الذيل \(14103r^{5000}\) و\(14100r^{5001}\) يكادان يتلاشيان معًا، ويظهر الجذر المطلوب بالضبط داخل هذه المنطقة الدقيقة جدًا.
الصيغة الكسرية تبدو وكأنها تملك مشكلة عند \(r=1\)، لكن هذه مجرد نقطة قابلة للإزالة؛ فالتعريف الأصلي ليس إلا مجموعًا منتهيًا لكثير حدود، لذا تكون الدالة نفسها منتظمة تمامًا هناك. مثال عملي مباشر هو
$$s_{5000}(1)=\sum_{k=1}^{5000}(900-3k)=900\cdot 5000-3\cdot\frac{5000\cdot 5001}{2}=-33{,}007{,}500.$$
هذه القيمة أعلى بكثير من الهدف \(-6\times 10^{11}\)، ولذلك يجب أن يكون الحل إلى يمين 1. وهذه الهوية الدقيقة نفسها تصلح أيضًا كنقطة فحص للتأكد من صحة منطق الجمع قبل بدء البحث العددي.
عند الطرف الأيمن يصبح الذيل السالب عالي القوى هو المسيطر. وفي الصيغة المغلقة يظهر المساهم الأهم على صورة
$$14103r^{5000}-14100r^{5001}=14100r^{5000}\left(\frac{14103}{14100}-r\right).$$
بمجرد أن يصبح \(r\) أكبر بوضوح من \(14103/14100\approx 1.000212766\)، يصير هذا المقدار سالبًا، وعند \(r=1.2\) يكون حجمه هائلًا. هذا يدفع المجموع كله إلى ما دون \(-6\times 10^{11}\) بكثير. وبما أن \(s_{5000}(r)\) دالة متصلة، فلا بد من وجود جذر واحد على الأقل داخل المجال \([1,1.2]\).
وتعتمد التطبيقات أيضًا على حقيقة خاصة بهذه المسألة، وهي أن المجموع يعبر الهدف مرة واحدة فقط داخل هذا المجال، ولذلك يمكن تضييق المجال بأمان بواسطة التنصيف.
حتى بعد الوصول إلى الصيغة المغلقة، تبقى المعادلة \(s_{5000}(r)=-600000000000\) مسألة من الدرجة 4999 في \(r\). لا يوجد اختصار رمزي عملي للجذر الدقيق، ولا حاجة إلى طرق تعتمد على المشتقة لأن مجال البحث معروف أصلًا. عندما تكون الدالة متصلة وتملك عبورًا واحدًا فقط، فإن التنصيف هو الخيار الأبسط والأكثر ثباتًا.
تتجنب تطبيقات C++ وPython وJava استخدام الصيغة الكسرية مباشرة أثناء التقييم العددي. بدلًا من ذلك تبني المجموع في مرور واحد: تبدأ القوة الحالية من 1 ثم تُضرب في \(r\) بعد كل حد. وإذا كتبنا \(P_k=r^{k-1}\)، فإن التحديثات تصبح
$$P_1=1,\qquad P_{k+1}=rP_k,\qquad S_k=S_{k-1}+(900-3k)P_k.$$
بعد \(k\) خطوات تكون الملاحظة الثابتة دقيقة تمامًا: \(S_k=s_k(r)\)، والقوة المخزنة للخطوة التالية هي \(r^k\). هذه الطريقة تطابق التعريف الرياضي حدًا بحد، كما أنها تتجنب الإلغاء العددي الذي قد يظهر قرب \(r=1\) عند استعمال الصيغة التي تحتوي على المقام \((1-r)^2\).
كل تقييم للقيمة \(s_{5000}(r)\) يمر على الحدود الخمسة آلاف مرة واحدة فقط. لذلك فالنواة العددية ليست أكثر من سلسلة من الضرب والجمع المتكرر، من دون جدول قوى ومن دون أي تعقيد إضافي في البنية.
يبدأ الحل العددي بحد أدنى يساوي 1 وحد أعلى يساوي 1.2. في كل دورة يحسب نقطة المنتصف ثم يقيّم المجموع عندها. إذا ظل المجموع في المنتصف أكبر من الهدف، فهذا يعني أن الجذر يقع أبعد إلى اليمين، فيُرفع الحد الأدنى؛ وإلا يُخفض الحد الأعلى. والثابت الأساسي هنا هو أن الطرف الأيسر يبقى دائمًا في جهة "المجموع ما زال أكبر من المطلوب"، بينما يبقى الطرف الأيمن في جهة "المجموع أصبح أصغر من المطلوب".
بعد 200 خطوة تنصيف، يصبح عرض المجال أصغر بكثير من \(10^{-12}\)، ولذلك يكون طباعة المنتصف إلى 12 منزلة عشرية أمرًا آمنًا. الفكرة العددية الأساسية واحدة في اللغات الثلاث؛ وإحدى النسخ تضيف فقط إمكانية تمرير معاملات المسألة اختياريًا والتحقق من هوية \(r=1\) قبل بدء البحث.
تكلفة تقييم واحد للسلسلة هي \(O(n)\) زمنًا و\(O(1)\) ذاكرة. ومع \(n=5000\) و200 خطوة تنصيف ثابتة، فإن الحل الكامل ينفذ تقريبًا \(5000\times 200=1{,}000{,}000\) عملية تحديث للحدود، لذا يكون الزمن العملي صغيرًا جدًا.
وبصيغةٍ عامة، إذا رمزنا لعدد خطوات التنصيف بـ \(I\)، فإن التعقيد الكلي هو \(O(nI)\) زمنًا و\(O(1)\) مساحةً. وبما أن \(I\) ثابت في هذه المسألة، فإن التنفيذ خطي فعليًا بالنسبة إلى \(n\).