For each integer \(n\) with \(3 \le n \le 50\), we choose uniformly at random an ordered \(n\)-tuple of positive integers \((\ell_1,\dots,\ell_n)\) satisfying
$$\ell_1+\cdots+\ell_n=2n-3.$$
For that tuple, let \(A_{\max}(\ell_1,\dots,\ell_n)\) be the largest area of a simple polygon with exactly those side lengths. The quantity for one fixed \(n\) is
$$\mathbb{E}_n=\frac{1}{\binom{2n-4}{n-1}}\sum_{\substack{\ell_1+\cdots+\ell_n=2n-3\\ \ell_i\ge 1}} A_{\max}(\ell_1,\dots,\ell_n),$$
and the problem asks for
$$S=\sum_{n=3}^{50}\mathbb{E}_n.$$
A brute-force scan over all ordered tuples is far too expensive. The implementation therefore groups tuples by side-length multiplicities, solves one cyclic-polygon optimization problem for each multiset, and weights it by the correct probability.
The whole solution rests on two facts: the random model is a uniform composition model, and for fixed side lengths the maximal-area polygon is cyclic.
Write every side as
$$\ell_i=1+e_i,\qquad e_i\in\mathbb{Z}_{\ge 0},\qquad \sum_{i=1}^{n} e_i=n-3=:E.$$
So the random input for one \(n\) is exactly a uniform ordered composition of \(E\) into \(n\) nonnegative parts. By stars and bars, the total number of outcomes is
$$\binom{E+n-1}{n-1}=\binom{2n-4}{n-1}.$$
This parametrization also shows that every sampled tuple can form a polygon: the largest possible side is \(1+E=n-2\), while the other \(n-1\) sides sum to at least \(n-1\).
For \(r\ge 1\), let \(c_r\) be the number of sides with excess \(r\), so those sides have length \(r+1\). Let \(c_0\) be the number of sides of length \(1\). Then
$$\sum_{r\ge 1} r\,c_r=E,\qquad c_0=n-\sum_{r\ge 1} c_r.$$
The data \((c_1,c_2,\dots)\) is just a partition of \(E\), so the program enumerates partitions rather than all ordered tuples. For one multiset, the number of orderings is the multinomial count
$$\frac{n!}{c_0!\prod_{r\ge 1} c_r!},$$
hence its probability is
$$P(c_0,c_1,c_2,\dots)=\frac{n!}{c_0!\prod_{r\ge 1} c_r!}\cdot \binom{2n-4}{n-1}^{-1}.$$
This compression is valid because the maximal area depends only on the multiset of side lengths, not on their order in the random tuple.
For a fixed multiset of side lengths, the maximal-area polygon is cyclic. Let \(R\) be its circumradius, and for each side define the half-angle of the corresponding minor central angle by
$$\alpha_i(R)=\arcsin\left(\frac{\ell_i}{2R}\right),\qquad R\ge \frac{\max_i \ell_i}{2}.$$
If the circumcenter lies inside the polygon, every side uses a minor arc. Then the central angles sum to \(2\pi\), so
$$2\sum_i \alpha_i(R)=2\pi \qquad\Longleftrightarrow\qquad \sum_i \alpha_i(R)=\pi.$$
Each \(\alpha_i(R)\) decreases as \(R\) grows, so a minor-arc solution exists exactly when the minimal admissible radius \(R_0=\max_i \ell_i/2\) still satisfies
$$\sum_i \alpha_i(R_0)\ge \pi.$$
If \(\sum_i \alpha_i(R_0)<\pi\), the maximizing cyclic polygon cannot place every side on a minor arc. In that case the unique longest side uses the major arc, while all other sides still use minor arcs.
If \(\alpha_{\max}(R)\) is the half-angle attached to that longest side, the full-angle condition becomes
$$2\sum_{i\ne \max}\alpha_i(R)+\bigl(2\pi-2\alpha_{\max}(R)\bigr)=2\pi,$$
which simplifies to
$$\sum_i \alpha_i(R)=2\alpha_{\max}(R).$$
So in both regimes the geometry is reduced to a single scalar root search in \(R\): either \(\sum_i \alpha_i(R)-\pi=0\) or \(\sum_i \alpha_i(R)-2\alpha_{\max}(R)=0\).
For one side \(\ell_i\), the isosceles triangle formed by the center and the chord has area
$$A_i(R)=\frac{1}{2}R^2\sin\bigl(2\alpha_i(R)\bigr)=\frac{\ell_i}{4}\sqrt{4R^2-\ell_i^2}.$$
Therefore, in the all-minor case,
$$A_{\max}=\sum_i A_i(R).$$
In the major-arc case, the longest side contributes with opposite orientation, so the area becomes
$$A_{\max}=\left|\sum_i A_i(R)-2A_L(R)\right|.$$
Finally, the expectation for one \(n\) is
$$\mathbb{E}_n=\sum_{(c_r)} P(c_0,c_1,c_2,\dots)\,A_{\max}(c_0,c_1,c_2,\dots),$$
and the required answer is \(S=\sum_{n=3}^{50}\mathbb{E}_n\).
Here \(E=n-3=1\), so the total number of ordered outcomes is
$$\binom{2n-4}{n-1}=\binom{4}{3}=4.$$
There is only one multiset of side lengths, namely \(\{2,1,1,1\}\), and it appears in all four orderings, so its probability is \(1\).
The longest side has length \(2\), so the minimal admissible radius is \(R_0=1\). At that radius,
$$\alpha(2)=\arcsin(1)=\frac{\pi}{2},\qquad \alpha(1)=\arcsin\left(\frac{1}{2}\right)=\frac{\pi}{6},$$
and therefore
$$\alpha(2)+3\alpha(1)=\frac{\pi}{2}+3\cdot\frac{\pi}{6}=\pi.$$
So the minor-arc equation is already satisfied at \(R=1\). The maximal area is then
$$A=\frac{2}{4}\sqrt{4-4}+3\cdot \frac{1}{4}\sqrt{4-1}=\frac{3\sqrt{3}}{4}\approx 1.299038,$$
which matches the intermediate validation value produced by the implementation.
The C++, Python, and Java implementations follow the same mathematical plan. First they precompute logarithms of factorials, which lets them evaluate multinomial probabilities without overflow. For each \(n\), they set \(E=n-3\) and recursively enumerate all partitions of \(E\); each partition directly represents one side-length multiset.
For every multiset, the implementation computes the logarithmic weight, converts it to a probability, and determines the longest side. It then tests the minimal admissible radius \(R_0=\max \ell_i/2\) to decide whether the minor-arc equation has a solution. After that, it brackets the correct root by increasing an upper bound until the sign changes, and refines the root with a Newton step guarded by bisection.
The derivative used in the Newton update is
$$\alpha_i'(R)=-\frac{\ell_i}{R\sqrt{4R^2-\ell_i^2}},$$
so one scan over the side multiplicities is enough to obtain both the function value and its derivative. Once \(R\) is known, the implementation converts each chord to its triangle contribution, applies the major-arc sign correction if necessary, multiplies by the multiset probability, accumulates \(\mathbb{E}_n\), and finally sums all \(\mathbb{E}_n\) from \(3\) to \(50\).
For fixed \(n\), let \(E=n-3\), and let \(p(E)\) be the partition number of \(E\). The program generates exactly one state per partition, so there are \(p(E)\) geometric evaluations for that \(n\). Each evaluation scans the distinct side lengths a constant number of times and performs a bounded root search, which yields \(O(EI)\) work per partition, where \(I\) is the iteration count of the numeric solver.
Thus the time cost for one \(n\) is
$$O\bigl(p(E)\,E\,I\bigr),$$
and the memory use is \(O(E)\) for the multiplicity data, plus a small \(O(n)\) table of logarithmic factorials. Since the problem only needs \(n\le 50\), we have \(E\le 47\), so this exhaustive weighted enumeration is entirely practical.
Für jedes \(n\) mit \(3 \le n \le 50\) wird ein geordnetes \(n\)-Tupel positiver ganzer Zahlen \((\ell_1,\dots,\ell_n)\) gleichverteilt unter der Nebenbedingung
$$\ell_1+\cdots+\ell_n=2n-3$$
gewählt. Für dieses Tupel sei \(A_{\max}(\ell_1,\dots,\ell_n)\) die größtmögliche Fläche eines einfachen Polygons mit genau diesen Seitenlängen. Für festes \(n\) gilt dann
$$\mathbb{E}_n=\frac{1}{\binom{2n-4}{n-1}}\sum_{\substack{\ell_1+\cdots+\ell_n=2n-3\\ \ell_i\ge 1}} A_{\max}(\ell_1,\dots,\ell_n),$$
und gesucht ist
$$S=\sum_{n=3}^{50}\mathbb{E}_n.$$
Direktes Durchgehen aller geordneten Tupel wäre zu teuer. Deshalb bündelt die Lösung Tupel mit demselben Seitenlängen-Multiset, löst pro Multiset genau ein geometrisches Optimierungsproblem und gewichtet das Ergebnis mit der korrekten Wahrscheinlichkeit.
Die Methode verbindet ein Kombinatorik-Modell für die Zufallsseiten mit dem Satz, dass bei festen Seitenlängen das flächenmaximale Polygon zyklisch ist.
Schreibe jede Seite als
$$\ell_i=1+e_i,\qquad e_i\in\mathbb{Z}_{\ge 0},\qquad \sum_{i=1}^{n} e_i=n-3=:E.$$
Damit ist die Zufallswahl für ein festes \(n\) genau eine gleichverteilte geordnete Komposition von \(E\) in \(n\) nichtnegative Teile. Mit Stars-and-Bars erhält man insgesamt
$$\binom{E+n-1}{n-1}=\binom{2n-4}{n-1}$$
Möglichkeiten. Gleichzeitig sieht man sofort, dass jede Stichprobe ein Polygon zulässt: Die längste mögliche Seite ist \(1+E=n-2\), die übrigen \(n-1\) Seiten summieren sich aber auf mindestens \(n-1\).
Für \(r\ge 1\) sei \(c_r\) die Anzahl der Seiten mit Exzess \(r\), also mit Länge \(r+1\). Außerdem sei \(c_0\) die Anzahl der Seiten der Länge \(1\). Dann gilt
$$\sum_{r\ge 1} r\,c_r=E,\qquad c_0=n-\sum_{r\ge 1} c_r.$$
Die Daten \((c_1,c_2,\dots)\) entsprechen genau einer Partition von \(E\). Daher enumeriert das Programm Partitionen statt aller geordneten Tupel. Für ein festes Multiset ist die Zahl der Anordnungen der Multinomialkoeffizient
$$\frac{n!}{c_0!\prod_{r\ge 1} c_r!},$$
also hat dieses Multiset die Wahrscheinlichkeit
$$P(c_0,c_1,c_2,\dots)=\frac{n!}{c_0!\prod_{r\ge 1} c_r!}\cdot \binom{2n-4}{n-1}^{-1}.$$
Diese Kompression ist korrekt, weil die maximale Fläche nur vom Multiset der Seitenlängen abhängt und nicht von deren Reihenfolge im zufälligen Tupel.
Für ein fixes Seitenlängen-Multiset ist das flächenmaximale Polygon zyklisch. Sei \(R\) sein Umkreisradius, und definiere für jede Seite die halbe zugehörige kleine Zentriwinkelhälfte durch
$$\alpha_i(R)=\arcsin\left(\frac{\ell_i}{2R}\right),\qquad R\ge \frac{\max_i \ell_i}{2}.$$
Liegt der Umkreismittelpunkt im Polygon, dann gehören alle Seiten zu kleinen Bögen. Die Zentriwinkel summieren sich zu \(2\pi\), also
$$2\sum_i \alpha_i(R)=2\pi \qquad\Longleftrightarrow\qquad \sum_i \alpha_i(R)=\pi.$$
Da jede Funktion \(\alpha_i(R)\) mit wachsendem \(R\) abnimmt, existiert eine Lösung im Small-Arc-Fall genau dann, wenn bereits der kleinste zulässige Radius \(R_0=\max_i \ell_i/2\) noch
$$\sum_i \alpha_i(R_0)\ge \pi$$
erfüllt.
Falls \(\sum_i \alpha_i(R_0)<\pi\) gilt, kann das Maximum nicht mit lauter kleinen Bögen erreicht werden. Dann verwendet die eindeutig längste Seite den großen Bogen, alle übrigen Seiten bleiben auf kleinen Bögen.
Bezeichnet \(\alpha_{\max}(R)\) die Halbwinkelgröße dieser längsten Seite, so lautet die volle Winkelsumme
$$2\sum_{i\ne \max}\alpha_i(R)+\bigl(2\pi-2\alpha_{\max}(R)\bigr)=2\pi,$$
also äquivalent
$$\sum_i \alpha_i(R)=2\alpha_{\max}(R).$$
Damit reduziert sich die gesamte Geometrie in beiden Regimen auf eine skalare Nullstellensuche: entweder \(\sum_i \alpha_i(R)-\pi=0\) oder \(\sum_i \alpha_i(R)-2\alpha_{\max}(R)=0\).
Für eine einzelne Seite \(\ell_i\) hat das gleichschenklige Dreieck aus Mittelpunkt und Sehne die Fläche
$$A_i(R)=\frac{1}{2}R^2\sin\bigl(2\alpha_i(R)\bigr)=\frac{\ell_i}{4}\sqrt{4R^2-\ell_i^2}.$$
Im reinen Minor-Fall ist daher
$$A_{\max}=\sum_i A_i(R).$$
Im Major-Fall trägt die längste Seite mit umgekehrter Orientierung bei, also
$$A_{\max}=\left|\sum_i A_i(R)-2A_L(R)\right|.$$
Damit folgt für festes \(n\)
$$\mathbb{E}_n=\sum_{(c_r)} P(c_0,c_1,c_2,\dots)\,A_{\max}(c_0,c_1,c_2,\dots),$$
und insgesamt \(S=\sum_{n=3}^{50}\mathbb{E}_n\).
Hier ist \(E=n-3=1\), also gibt es insgesamt
$$\binom{2n-4}{n-1}=\binom{4}{3}=4$$
geordnete Zufallsfälle. Das einzige Seitenlängen-Multiset ist \(\{2,1,1,1\}\), und es tritt in allen vier Anordnungen auf, also mit Wahrscheinlichkeit \(1\).
Die längste Seite hat Länge \(2\), also ist der kleinste zulässige Radius \(R_0=1\). Dort gilt
$$\alpha(2)=\arcsin(1)=\frac{\pi}{2},\qquad \alpha(1)=\arcsin\left(\frac{1}{2}\right)=\frac{\pi}{6},$$
und damit
$$\alpha(2)+3\alpha(1)=\frac{\pi}{2}+3\cdot\frac{\pi}{6}=\pi.$$
Die Minor-Gleichung ist also schon bei \(R=1\) erfüllt. Die maximale Fläche ist dann
$$A=\frac{2}{4}\sqrt{4-4}+3\cdot \frac{1}{4}\sqrt{4-1}=\frac{3\sqrt{3}}{4}\approx 1.299038,$$
genau der Zwischenwert, den die Implementierung zur Kontrolle reproduziert.
Die C++-, Python- und Java-Implementierungen folgen demselben mathematischen Plan. Zuerst werden Logarithmen von Fakultäten vorab berechnet, damit sich die multinomialen Wahrscheinlichkeiten numerisch stabil und ohne Überlauf auswerten lassen. Für jedes \(n\) setzt die Implementierung \(E=n-3\) und erzeugt rekursiv alle Partitionen von \(E\); jede Partition steht direkt für ein Seitenlängen-Multiset.
Für jedes Multiset berechnet die Implementierung sein logarithmisches Gewicht, wandelt dieses in eine Wahrscheinlichkeit um und bestimmt die längste Seite. Anschließend prüft sie beim minimal zulässigen Radius \(R_0=\max \ell_i/2\), ob die Minor-Gleichung lösbar ist. Dann wird die richtige Nullstelle zunächst durch Vergrößern einer oberen Schranke eingerahmt und schließlich mit einem Newton-Schritt, abgesichert durch Bisektion, verfeinert.
Die dazu verwendete Ableitung lautet
$$\alpha_i'(R)=-\frac{\ell_i}{R\sqrt{4R^2-\ell_i^2}}.$$
Damit genügt pro Radiusauswertung ein Durchlauf über die Seitenhäufigkeiten, um sowohl Funktionswert als auch Ableitung zu erhalten. Sobald \(R\) feststeht, werden die Dreiecksbeiträge aller Sehnen summiert, gegebenenfalls die Major-Arc-Korrektur angewandt, mit der Wahrscheinlichkeit multipliziert, zu \(\mathbb{E}_n\) addiert und am Ende über alle \(n\) von \(3\) bis \(50\) aufsummiert.
Für festes \(n\) sei \(E=n-3\) und \(p(E)\) die Partitionszahl von \(E\). Das Programm erzeugt genau einen Zustand pro Partition, also \(p(E)\) geometrische Auswertungen. Jede Auswertung scannt die verschiedenen Seitenlängen nur eine konstante Anzahl von Malen und führt eine beschränkte Nullstellensuche aus; das ergibt \(O(EI)\) Arbeit pro Partition, wobei \(I\) die Iterationszahl des numerischen Solvers bezeichnet.
Damit kostet ein festes \(n\)
$$O\bigl(p(E)\,E\,I\bigr),$$
während der Speicherbedarf \(O(E)\) für die Häufigkeitsdaten plus eine kleine \(O(n)\)-Tabelle logarithmischer Fakultäten beträgt. Da hier nur \(n\le 50\) vorkommt und somit \(E\le 47\), ist diese vollständige gewichtete Enumeration gut beherrschbar.
Her \(n\) için, \(3 \le n \le 50\) aralığında,
$$\ell_1+\cdots+\ell_n=2n-3$$
koşulunu sağlayan pozitif tam sayılı sıralı \(n\)-liler \((\ell_1,\dots,\ell_n)\) eşit olasılıkla seçilir. Bu \(n\)-li için \(A_{\max}(\ell_1,\dots,\ell_n)\), tam olarak bu kenar uzunluklarına sahip basit bir çokgenin alabileceği en büyük alan olsun. Sabit bir \(n\) için aranan beklenti
$$\mathbb{E}_n=\frac{1}{\binom{2n-4}{n-1}}\sum_{\substack{\ell_1+\cdots+\ell_n=2n-3\\ \ell_i\ge 1}} A_{\max}(\ell_1,\dots,\ell_n),$$
ve nihai hedef
$$S=\sum_{n=3}^{50}\mathbb{E}_n$$
toplamıdır. Doğrudan bütün sıralı dizileri denemek çok pahalı olduğundan, çözüm aynı kenar çokluğuna sahip durumları birleştirir, her çokluk için tek bir geometrik optimizasyon çözer ve sonucu doğru olasılıkla ağırlıklandırır.
Yöntem iki ana gözleme dayanır: rassal model bir bileşim modelidir ve sabit kenarlar için maksimum alan çevrel bir çokgende elde edilir.
Her kenarı
$$\ell_i=1+e_i,\qquad e_i\in\mathbb{Z}_{\ge 0},\qquad \sum_{i=1}^{n} e_i=n-3=:E$$
şeklinde yazalım. Böylece sabit bir \(n\) için rastgele seçim, \(E\)'nin \(n\) tane negatif olmayan parçaya eşit olasılıklı sıralı ayrışımı olur. Stars and bars sonucu toplam durum sayısı
$$\binom{E+n-1}{n-1}=\binom{2n-4}{n-1}$$
olur. Bu gösterim aynı zamanda her örneğin gerçekten bir çokgen oluşturabildiğini de gösterir: en büyük kenar en fazla \(1+E=n-2\) olabilir, geri kalan \(n-1\) kenarın toplamı ise en az \(n-1\)'dir.
\(r\ge 1\) için \(c_r\), fazlalığı \(r\) olan, yani uzunluğu \(r+1\) olan kenar sayısı olsun. Ayrıca \(c_0\), uzunluğu \(1\) olan kenar sayısını göstersin. O zaman
$$\sum_{r\ge 1} r\,c_r=E,\qquad c_0=n-\sum_{r\ge 1} c_r.$$
\((c_1,c_2,\dots)\) verisi tam olarak \(E\)'nin bir partition'ına karşılık gelir. Bu yüzden program bütün sıralı dizileri değil, partition'ları gezer. Belirli bir çokluk için sıralama sayısı multinom katsayısıdır:
$$\frac{n!}{c_0!\prod_{r\ge 1} c_r!}.$$
Dolayısıyla bu çokluğun olasılığı
$$P(c_0,c_1,c_2,\dots)=\frac{n!}{c_0!\prod_{r\ge 1} c_r!}\cdot \binom{2n-4}{n-1}^{-1}$$
olur. Bu sıkıştırma geçerlidir çünkü maksimum alan kenarların sırasına değil, sadece kenar uzunluklarının çokluğuna bağlıdır.
Sabit bir kenar çokluğu için maksimum alanlı çokgen çevreldir. \(R\) çevrel yarıçap olsun ve her kenar için ilgili küçük merkez açısının yarısını
$$\alpha_i(R)=\arcsin\left(\frac{\ell_i}{2R}\right),\qquad R\ge \frac{\max_i \ell_i}{2}$$
olarak tanımlayalım. Eğer merkez çokgenin içinde ise bütün kenarlar küçük yay kullanır. O zaman merkez açıların toplamı \(2\pi\) olur ve
$$2\sum_i \alpha_i(R)=2\pi \qquad\Longleftrightarrow\qquad \sum_i \alpha_i(R)=\pi$$
elde edilir. Her \(\alpha_i(R)\) büyüyen \(R\) ile azaldığından, küçük-yay çözümü ancak ve ancak en küçük izin verilen yarıçap \(R_0=\max_i \ell_i/2\) için
$$\sum_i \alpha_i(R_0)\ge \pi$$
sağlanıyorsa vardır.
Eğer \(\sum_i \alpha_i(R_0)<\pi\) ise, maksimum alan bütün kenarları küçük yaylarda tutamaz. Bu durumda tek bir en uzun kenar büyük yayı kullanır, diğerleri küçük yaylarda kalır.
Bu en uzun kenarın yarı açı değeri \(\alpha_{\max}(R)\) ise toplam açı koşulu
$$2\sum_{i\ne \max}\alpha_i(R)+\bigl(2\pi-2\alpha_{\max}(R)\bigr)=2\pi$$
olur; bu da
$$\sum_i \alpha_i(R)=2\alpha_{\max}(R)$$
şeklinde sadeleşir. Böylece iki rejimde de problem tek değişkenli bir kök aramasına iner: ya \(\sum_i \alpha_i(R)-\pi=0\) ya da \(\sum_i \alpha_i(R)-2\alpha_{\max}(R)=0\).
Uzunluğu \(\ell_i\) olan bir kiriş için, merkezle birlikte oluşan ikizkenar üçgenin alanı
$$A_i(R)=\frac{1}{2}R^2\sin\bigl(2\alpha_i(R)\bigr)=\frac{\ell_i}{4}\sqrt{4R^2-\ell_i^2}$$
olur. Buna göre tamamen küçük-yay durumunda
$$A_{\max}=\sum_i A_i(R)$$
yazılır. Büyük-yay durumunda ise en uzun kenarın katkısı ters işaretle gelir:
$$A_{\max}=\left|\sum_i A_i(R)-2A_L(R)\right|.$$
Sonuç olarak sabit bir \(n\) için beklenti
$$\mathbb{E}_n=\sum_{(c_r)} P(c_0,c_1,c_2,\dots)\,A_{\max}(c_0,c_1,c_2,\dots)$$
ve genel cevap \(S=\sum_{n=3}^{50}\mathbb{E}_n\) olur.
Burada \(E=n-3=1\) olduğundan toplam sıralı örnek sayısı
$$\binom{2n-4}{n-1}=\binom{4}{3}=4$$
olur. Tek kenar çokluğu \(\{2,1,1,1\}\)'dir ve dört sıralamanın hepsinde aynı çokluk görüldüğü için olasılığı \(1\)'dir.
En uzun kenar \(2\) olduğundan en küçük izinli yarıçap \(R_0=1\) olur. Bu yarıçapta
$$\alpha(2)=\arcsin(1)=\frac{\pi}{2},\qquad \alpha(1)=\arcsin\left(\frac{1}{2}\right)=\frac{\pi}{6}$$
ve dolayısıyla
$$\alpha(2)+3\alpha(1)=\frac{\pi}{2}+3\cdot\frac{\pi}{6}=\pi$$
elde edilir. Yani küçük-yay denklemi zaten \(R=1\)'de sağlanır. Maksimum alan
$$A=\frac{2}{4}\sqrt{4-4}+3\cdot \frac{1}{4}\sqrt{4-1}=\frac{3\sqrt{3}}{4}\approx 1.299038$$
olur; bu da uygulamanın ara doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı matematiksel planı izler. Önce faktöriyel logaritmaları önceden hesaplanır; böylece multinom olasılıkları taşma olmadan ve sayısal olarak kararlı biçimde hesaplanır. Her \(n\) için uygulama \(E=n-3\) alır ve \(E\)'nin tüm partition'larını özyinelemeli olarak üretir; her partition doğrudan bir kenar çokluğunu temsil eder.
Her çokluk için logaritmik ağırlık hesaplanır, bu ağırlık olasılığa çevrilir ve en uzun kenar belirlenir. Ardından en küçük izinli yarıçap \(R_0=\max \ell_i/2\) üzerinde küçük-yay denkleminin çözülebilir olup olmadığı test edilir. Sonra uygun denklemin kökü, önce üst sınır büyütülerek aralık içine alınır, ardından bisection ile güvenceye alınmış Newton adımlarıyla inceltilir.
Newton güncellemesinde kullanılan türev
$$\alpha_i'(R)=-\frac{\ell_i}{R\sqrt{4R^2-\ell_i^2}}$$
olduğundan, kenar çoklukları üzerinden tek bir tarama hem fonksiyon değerini hem de türevini verir. \(R\) bulunduğunda bütün kiriş katkıları toplanır, gerekiyorsa büyük-yay işaret düzeltmesi uygulanır, sonuç olasılıkla çarpılır, \(\mathbb{E}_n\)'ye eklenir ve son aşamada \(3\) ile \(50\) arasındaki tüm \(n\) değerleri toplanır.
Sabit bir \(n\) için \(E=n-3\) ve \(p(E)\), \(E\)'nin partition sayısı olsun. Program her partition için tam bir geometrik değerlendirme yapar; dolayısıyla o \(n\) için toplam \(p(E)\) durum vardır. Her değerlendirme farklı kenar uzunluklarını sabit sayıda tarar ve sınırlı sayıda kök arama adımı kullanır; bu yüzden partition başına maliyet \(O(EI)\), burada \(I\) sayısal çözücünün iterasyon sayısıdır.
Buna göre sabit bir \(n\) için toplam süre
$$O\bigl(p(E)\,E\,I\bigr)$$
olur. Bellek kullanımı ise çokluk verileri için \(O(E)\), ayrıca küçük bir \(O(n)\) log-faktöriyel tablosudur. Problemde yalnızca \(n\le 50\) gerektiğinden \(E\le 47\) olur; bu yüzden bu tam ağırlıklı tarama pratikte uygundur.
Para cada \(n\) con \(3 \le n \le 50\), se elige de manera uniforme una \(n\)-tupla ordenada de enteros positivos \((\ell_1,\dots,\ell_n)\) que cumple
$$\ell_1+\cdots+\ell_n=2n-3.$$
Para esa tupla, sea \(A_{\max}(\ell_1,\dots,\ell_n)\) el área máxima de un polígono simple con exactamente esas longitudes de lado. Para un \(n\) fijo se define
$$\mathbb{E}_n=\frac{1}{\binom{2n-4}{n-1}}\sum_{\substack{\ell_1+\cdots+\ell_n=2n-3\\ \ell_i\ge 1}} A_{\max}(\ell_1,\dots,\ell_n),$$
y el problema pide
$$S=\sum_{n=3}^{50}\mathbb{E}_n.$$
Enumerar todas las tuplas ordenadas sería demasiado costoso. Por eso la solución agrupa las tuplas por multiconjuntos de longitudes, resuelve un único problema geométrico por cada multiconjunto y lo pondera con la probabilidad multinomial correcta.
La estrategia combina una descripción combinatoria del modelo aleatorio con el hecho geométrico de que, para lados fijos, el polígono de área máxima es cíclico.
Escribimos cada lado como
$$\ell_i=1+e_i,\qquad e_i\in\mathbb{Z}_{\ge 0},\qquad \sum_{i=1}^{n} e_i=n-3=:E.$$
Así, para un \(n\) fijo, el muestreo uniforme equivale a escoger una composición ordenada uniforme de \(E\) en \(n\) partes no negativas. Por stars and bars, el número total de resultados es
$$\binom{E+n-1}{n-1}=\binom{2n-4}{n-1}.$$
Además, esta parametrización muestra que toda muestra puede formar un polígono: el lado más largo posible es \(1+E=n-2\), mientras que la suma de los otros \(n-1\) lados es al menos \(n-1\).
Para \(r\ge 1\), sea \(c_r\) el número de lados con exceso \(r\), es decir, con longitud \(r+1\). Sea también \(c_0\) el número de lados de longitud \(1\). Entonces
$$\sum_{r\ge 1} r\,c_r=E,\qquad c_0=n-\sum_{r\ge 1} c_r.$$
Los datos \((c_1,c_2,\dots)\) forman exactamente una partición de \(E\), de modo que el programa enumera particiones en lugar de todas las tuplas ordenadas. Para un multiconjunto fijo, el número de ordenaciones es
$$\frac{n!}{c_0!\prod_{r\ge 1} c_r!},$$
y por lo tanto su probabilidad es
$$P(c_0,c_1,c_2,\dots)=\frac{n!}{c_0!\prod_{r\ge 1} c_r!}\cdot \binom{2n-4}{n-1}^{-1}.$$
Esta compresión es válida porque el área máxima depende solo del multiconjunto de lados, no del orden en que aparezcan en la tupla aleatoria.
Para un multiconjunto fijo de lados, el polígono de área máxima es cíclico. Sea \(R\) su circunradio y definamos, para cada lado, la mitad del ángulo central menor correspondiente por
$$\alpha_i(R)=\arcsin\left(\frac{\ell_i}{2R}\right),\qquad R\ge \frac{\max_i \ell_i}{2}.$$
Si el circuncentro está dentro del polígono, todos los lados usan arcos menores. Entonces la suma de los ángulos centrales es \(2\pi\), así que
$$2\sum_i \alpha_i(R)=2\pi \qquad\Longleftrightarrow\qquad \sum_i \alpha_i(R)=\pi.$$
Cada \(\alpha_i(R)\) decrece cuando \(R\) aumenta. Por ello, una solución de arco menor existe exactamente cuando en el radio mínimo admisible \(R_0=\max_i \ell_i/2\) todavía se cumple
$$\sum_i \alpha_i(R_0)\ge \pi.$$
Si \(\sum_i \alpha_i(R_0)<\pi\), el polígono óptimo no puede usar solo arcos menores. En ese caso, el lado más largo, que debe ser único, usa el arco mayor, mientras que los demás siguen usando arcos menores.
Si \(\alpha_{\max}(R)\) denota el medio ángulo asociado a ese lado más largo, la condición angular completa es
$$2\sum_{i\ne \max}\alpha_i(R)+\bigl(2\pi-2\alpha_{\max}(R)\bigr)=2\pi,$$
lo cual se simplifica a
$$\sum_i \alpha_i(R)=2\alpha_{\max}(R).$$
Así, en ambos regímenes la geometría se reduce a una búsqueda de raíz escalar en \(R\): o bien \(\sum_i \alpha_i(R)-\pi=0\), o bien \(\sum_i \alpha_i(R)-2\alpha_{\max}(R)=0\).
Para un lado \(\ell_i\), el triángulo isósceles formado por el centro y la cuerda tiene área
$$A_i(R)=\frac{1}{2}R^2\sin\bigl(2\alpha_i(R)\bigr)=\frac{\ell_i}{4}\sqrt{4R^2-\ell_i^2}.$$
Por tanto, en el caso completamente menor,
$$A_{\max}=\sum_i A_i(R).$$
En el caso de arco mayor, la contribución del lado más largo entra con orientación opuesta, y entonces
$$A_{\max}=\left|\sum_i A_i(R)-2A_L(R)\right|.$$
Finalmente, para un \(n\) fijo,
$$\mathbb{E}_n=\sum_{(c_r)} P(c_0,c_1,c_2,\dots)\,A_{\max}(c_0,c_1,c_2,\dots),$$
y la respuesta total es \(S=\sum_{n=3}^{50}\mathbb{E}_n\).
Aquí \(E=n-3=1\), así que el número total de resultados ordenados es
$$\binom{2n-4}{n-1}=\binom{4}{3}=4.$$
Solo existe un multiconjunto de longitudes, \(\{2,1,1,1\}\), y aparece en las cuatro ordenaciones posibles, de modo que su probabilidad es \(1\).
El lado más largo mide \(2\), por lo que el radio mínimo admisible es \(R_0=1\). En ese radio,
$$\alpha(2)=\arcsin(1)=\frac{\pi}{2},\qquad \alpha(1)=\arcsin\left(\frac{1}{2}\right)=\frac{\pi}{6},$$
y por tanto
$$\alpha(2)+3\alpha(1)=\frac{\pi}{2}+3\cdot\frac{\pi}{6}=\pi.$$
La ecuación de arcos menores ya queda satisfecha con \(R=1\). El área máxima es entonces
$$A=\frac{2}{4}\sqrt{4-4}+3\cdot \frac{1}{4}\sqrt{4-1}=\frac{3\sqrt{3}}{4}\approx 1.299038,$$
valor que coincide con la comprobación intermedia usada por la implementación.
Las implementaciones en C++, Python y Java siguen el mismo plan matemático. Primero precalculan logaritmos de factoriales, lo que permite evaluar probabilidades multinomiales sin desbordamientos. Para cada \(n\), la implementación fija \(E=n-3\) y genera recursivamente todas las particiones de \(E\); cada partición representa directamente un multiconjunto de longitudes.
Para cada multiconjunto, la implementación calcula su peso logarítmico, lo convierte en probabilidad y determina la longitud máxima. Luego prueba el radio mínimo admisible \(R_0=\max \ell_i/2\) para decidir si existe solución en el régimen de arcos menores. Después encierra la raíz correcta ampliando una cota superior hasta obtener un cambio de signo, y finalmente la refina con un paso de Newton protegido por bisección.
La derivada utilizada por Newton es
$$\alpha_i'(R)=-\frac{\ell_i}{R\sqrt{4R^2-\ell_i^2}}.$$
De ese modo, un solo recorrido sobre las multiplicidades de lados basta para obtener tanto el valor de la función como su derivada. Una vez conocido \(R\), la implementación suma las contribuciones triangulares de todas las cuerdas, aplica la corrección de signo del arco mayor cuando hace falta, multiplica por la probabilidad del multiconjunto, acumula \(\mathbb{E}_n\) y al final suma todos los valores desde \(n=3\) hasta \(n=50\).
Para un \(n\) fijo, sea \(E=n-3\) y \(p(E)\) el número de particiones de \(E\). El programa genera exactamente un estado por partición, así que hay \(p(E)\) evaluaciones geométricas para ese \(n\). Cada evaluación recorre las longitudes distintas un número constante de veces y ejecuta una búsqueda de raíz con un número acotado de iteraciones, lo que produce \(O(EI)\) trabajo por partición, donde \(I\) es el número de iteraciones del solucionador numérico.
Por tanto, el coste temporal para un \(n\) fijo es
$$O\bigl(p(E)\,E\,I\bigr),$$
mientras que la memoria es \(O(E)\) para las multiplicidades y un pequeño \(O(n)\) para la tabla de log-factoriales. Como solo se necesita \(n\le 50\), tenemos \(E\le 47\), y la enumeración exhaustiva ponderada resulta totalmente viable.
对每个满足 \(3 \le n \le 50\) 的整数 \(n\)，等概率地从所有正整数有序 \(n\) 元组 \((\ell_1,\dots,\ell_n)\) 中选取一个样本，并要求
$$\ell_1+\cdots+\ell_n=2n-3.$$
对于这组边长，记 \(A_{\max}(\ell_1,\dots,\ell_n)\) 为具有这些边长的简单多边形所能达到的最大面积。于是固定 \(n\) 时的期望为
$$\mathbb{E}_n=\frac{1}{\binom{2n-4}{n-1}}\sum_{\substack{\ell_1+\cdots+\ell_n=2n-3\\ \ell_i\ge 1}} A_{\max}(\ell_1,\dots,\ell_n),$$
题目要求的总量是
$$S=\sum_{n=3}^{50}\mathbb{E}_n.$$
如果直接枚举所有有序边长元组，数量会迅速爆炸。实现采用的思路是：先把边长按“多重集”归类，对每一种边长多重集只求解一次最大面积问题，再用正确的多项式系数概率进行加权。
整个解法把组合计数和几何最优化结合起来。组合部分来自整数拆分，几何部分来自“固定边长时最大面积多边形一定是圆内接多边形”这一事实。
把每条边写成
$$\ell_i=1+e_i,\qquad e_i\in\mathbb{Z}_{\ge 0},\qquad \sum_{i=1}^{n} e_i=n-3=:E.$$
这样一来，固定 \(n\) 时的随机模型就变成了：把 \(E\) 等概率地分配到 \(n\) 个非负位置上，也就是一个有序组合问题。由 stars and bars 可知，总样本数为
$$\binom{E+n-1}{n-1}=\binom{2n-4}{n-1}.$$
这个改写还有一个额外好处：它直接说明所有样本都能形成多边形。最长边最多是 \(1+E=n-2\)，而其余 \(n-1\) 条边的总和至少是 \(n-1\)，因此严格大于最长边。
对 \(r\ge 1\)，记 \(c_r\) 为“剩余量等于 \(r\)”的边的条数，这些边的长度就是 \(r+1\)。再记 \(c_0\) 为长度等于 \(1\) 的边数。于是有
$$\sum_{r\ge 1} r\,c_r=E,\qquad c_0=n-\sum_{r\ge 1} c_r.$$
\((c_1,c_2,\dots)\) 正好对应于 \(E\) 的一个整数分拆，所以程序枚举的是分拆，而不是全部有序元组。对于一个固定的边长多重集，其对应的有序排列数量是
$$\frac{n!}{c_0!\prod_{r\ge 1} c_r!},$$
因此该多重集的概率为
$$P(c_0,c_1,c_2,\dots)=\frac{n!}{c_0!\prod_{r\ge 1} c_r!}\cdot \binom{2n-4}{n-1}^{-1}.$$
之所以可以这样压缩，是因为最大面积只取决于边长的多重集，而不取决于这些边在随机有序元组中的排列顺序。
对于固定边长多重集，面积最大的多边形一定是圆内接多边形。设其外接圆半径为 \(R\)，并对每条边定义对应的小圆心角的一半：
$$\alpha_i(R)=\arcsin\left(\frac{\ell_i}{2R}\right),\qquad R\ge \frac{\max_i \ell_i}{2}.$$
如果圆心位于多边形内部，那么所有边都对应小弧。这时圆心角总和为 \(2\pi\)，于是
$$2\sum_i \alpha_i(R)=2\pi \qquad\Longleftrightarrow\qquad \sum_i \alpha_i(R)=\pi.$$
由于每个 \(\alpha_i(R)\) 都会随着 \(R\) 的增大而减小，所以“小弧方案”是否存在，只需检查最小允许半径 \(R_0=\max_i \ell_i/2\)。若
$$\sum_i \alpha_i(R_0)\ge \pi,$$
则存在小弧解；否则不存在。
如果 \(\sum_i \alpha_i(R_0)<\pi\)，说明最大面积构型不可能让所有边都落在小弧上。此时必须由唯一的最长边对应大弧，其余边仍对应小弧。
设这条最长边对应的半角为 \(\alpha_{\max}(R)\)，那么总角度条件变成
$$2\sum_{i\ne \max}\alpha_i(R)+\bigl(2\pi-2\alpha_{\max}(R)\bigr)=2\pi,$$
整理后得到
$$\sum_i \alpha_i(R)=2\alpha_{\max}(R).$$
因此无论是“小弧情形”还是“大弧情形”，几何部分最终都化为一个单变量求根问题：要么解 \(\sum_i \alpha_i(R)-\pi=0\)，要么解 \(\sum_i \alpha_i(R)-2\alpha_{\max}(R)=0\)。
对一条长度为 \(\ell_i\) 的弦，由圆心和该弦构成的等腰三角形面积为
$$A_i(R)=\frac{1}{2}R^2\sin\bigl(2\alpha_i(R)\bigr)=\frac{\ell_i}{4}\sqrt{4R^2-\ell_i^2}.$$
因此，在全部使用小弧时，最大面积就是
$$A_{\max}=\sum_i A_i(R).$$
如果存在一条最长边使用大弧，那么这条边对应的三角形贡献方向相反，于是面积应写成
$$A_{\max}=\left|\sum_i A_i(R)-2A_L(R)\right|.$$
最后，对固定 \(n\) 的期望可写为
$$\mathbb{E}_n=\sum_{(c_r)} P(c_0,c_1,c_2,\dots)\,A_{\max}(c_0,c_1,c_2,\dots),$$
而总答案则是 \(S=\sum_{n=3}^{50}\mathbb{E}_n\)。
此时 \(E=n-3=1\)，因此有序样本总数为
$$\binom{2n-4}{n-1}=\binom{4}{3}=4.$$
唯一可能的边长多重集是 \(\{2,1,1,1\}\)。它在四种有序排列中都出现一次，所以对应概率为 \(1\)。
最长边长度是 \(2\)，因此最小允许半径为 \(R_0=1\)。在这个半径下，
$$\alpha(2)=\arcsin(1)=\frac{\pi}{2},\qquad \alpha(1)=\arcsin\left(\frac{1}{2}\right)=\frac{\pi}{6},$$
于是
$$\alpha(2)+3\alpha(1)=\frac{\pi}{2}+3\cdot\frac{\pi}{6}=\pi.$$
这说明小弧方程在 \(R=1\) 时已经成立，不需要进入大弧情形。面积因此为
$$A=\frac{2}{4}\sqrt{4-4}+3\cdot \frac{1}{4}\sqrt{4-1}=\frac{3\sqrt{3}}{4}\approx 1.299038,$$
这正好与实现中的中间校验值一致。
C++、Python 和 Java 实现遵循同一套数学流程。首先预计算阶乘对数，这样就能稳定地计算多项式系数概率，而不会出现整数溢出。对每个 \(n\)，实现令 \(E=n-3\)，然后递归枚举 \(E\) 的所有整数分拆；每个分拆都直接对应一种边长多重集。
对每个多重集，实现先计算其对数权重，再转成概率，并找出最长边。随后在最小允许半径 \(R_0=\max \ell_i/2\) 处测试“小弧方程”是否有解。接着通过逐步放大上界来包住正确根，再使用带二分保护的 Newton 迭代进行细化。
Newton 迭代所用导数为
$$\alpha_i'(R)=-\frac{\ell_i}{R\sqrt{4R^2-\ell_i^2}}.$$
因此，每次对边长多重集扫描一遍，就能同时得到函数值和导数。确定 \(R\) 之后，实现把所有弦对应的三角形面积相加，如有需要再对大弧最长边做符号修正，乘上该多重集的概率，累加到 \(\mathbb{E}_n\)，最后再把 \(n=3\) 到 \(50\) 的全部期望相加。
对固定 \(n\)，令 \(E=n-3\)，令 \(p(E)\) 表示 \(E\) 的分拆数。程序对每个分拆恰好进行一次几何求值，所以该 \(n\) 的状态数就是 \(p(E)\)。每次求值都会对不同边长做常数次扫描，并执行一个迭代次数有上界的求根过程，因此每个分拆的代价是 \(O(EI)\)，其中 \(I\) 是数值求解器的迭代次数。
于是固定 \(n\) 的时间复杂度为
$$O\bigl(p(E)\,E\,I\bigr),$$
空间复杂度为存储边长个数信息所需的 \(O(E)\)，外加一个很小的 \(O(n)\) 阶乘对数表。由于题目只要求到 \(n\le 50\)，所以 \(E\le 47\)，这种穷举加权方式在这里是可行的。
Для каждого \(n\) в диапазоне \(3 \le n \le 50\) равновероятно выбирается упорядоченный набор положительных целых чисел \((\ell_1,\dots,\ell_n)\), удовлетворяющий условию
$$\ell_1+\cdots+\ell_n=2n-3.$$
Для этого набора обозначим через \(A_{\max}(\ell_1,\dots,\ell_n)\) наибольшую возможную площадь простого многоугольника с точно такими длинами сторон. Тогда для фиксированного \(n\)
$$\mathbb{E}_n=\frac{1}{\binom{2n-4}{n-1}}\sum_{\substack{\ell_1+\cdots+\ell_n=2n-3\\ \ell_i\ge 1}} A_{\max}(\ell_1,\dots,\ell_n),$$
а требуется вычислить
$$S=\sum_{n=3}^{50}\mathbb{E}_n.$$
Прямой перебор всех упорядоченных наборов слишком дорог. Поэтому решение объединяет наборы с одинаковым мультимножеством длин сторон, решает одну геометрическую задачу на каждое мультимножество и умножает результат на правильную мультиномиальную вероятность.
Основа решения двойная: случайная модель удобно описывается через композиции числа, а многоугольник максимальной площади при фиксированных сторонах всегда является вписанным в окружность.
Запишем каждую сторону в виде
$$\ell_i=1+e_i,\qquad e_i\in\mathbb{Z}_{\ge 0},\qquad \sum_{i=1}^{n} e_i=n-3=:E.$$
Тогда для фиксированного \(n\) случайный выбор превращается в равномерный выбор упорядоченной композиции числа \(E\) на \(n\) неотрицательных частей. По формуле stars and bars общее число исходов равно
$$\binom{E+n-1}{n-1}=\binom{2n-4}{n-1}.$$
Эта запись сразу показывает, что любой такой набор действительно задаёт многоугольник: максимальная возможная сторона равна \(1+E=n-2\), а сумма остальных \(n-1\) сторон не меньше \(n-1\).
Для \(r\ge 1\) обозначим через \(c_r\) число сторон с избытком \(r\), то есть со длиной \(r+1\). Через \(c_0\) обозначим число сторон длины \(1\). Тогда
$$\sum_{r\ge 1} r\,c_r=E,\qquad c_0=n-\sum_{r\ge 1} c_r.$$
Данные \((c_1,c_2,\dots)\) в точности задают разбиение числа \(E\), поэтому программа перебирает разбиения, а не все упорядоченные наборы. Для фиксированного мультимножества число упорядочений равно
$$\frac{n!}{c_0!\prod_{r\ge 1} c_r!},$$
и потому его вероятность равна
$$P(c_0,c_1,c_2,\dots)=\frac{n!}{c_0!\prod_{r\ge 1} c_r!}\cdot \binom{2n-4}{n-1}^{-1}.$$
Такое сжатие корректно, потому что максимальная площадь зависит только от мультимножества длин сторон, а не от их порядка в исходном случайном наборе.
Для фиксированного мультимножества сторон многоугольник максимальной площади является вписанным в окружность. Пусть \(R\) — радиус описанной окружности. Для каждой стороны введём половину соответствующего меньшего центрального угла:
$$\alpha_i(R)=\arcsin\left(\frac{\ell_i}{2R}\right),\qquad R\ge \frac{\max_i \ell_i}{2}.$$
Если центр окружности лежит внутри многоугольника, все стороны соответствуют меньшим дугам. Тогда сумма центральных углов равна \(2\pi\), то есть
$$2\sum_i \alpha_i(R)=2\pi \qquad\Longleftrightarrow\qquad \sum_i \alpha_i(R)=\pi.$$
Каждая функция \(\alpha_i(R)\) убывает по \(R\), поэтому решение в режиме меньших дуг существует тогда и только тогда, когда уже при минимально допустимом радиусе \(R_0=\max_i \ell_i/2\) выполнено
$$\sum_i \alpha_i(R_0)\ge \pi.$$
Если \(\sum_i \alpha_i(R_0)<\pi\), то конфигурация максимальной площади не может использовать только малые дуги. Тогда единственная самая длинная сторона идёт по большой дуге, а все остальные стороны остаются на малых дугах.
Если \(\alpha_{\max}(R)\) — половина угла, соответствующая этой самой длинной стороне, то условие на полную сумму углов принимает вид
$$2\sum_{i\ne \max}\alpha_i(R)+\bigl(2\pi-2\alpha_{\max}(R)\bigr)=2\pi,$$
что эквивалентно формуле
$$\sum_i \alpha_i(R)=2\alpha_{\max}(R).$$
Итак, в обоих режимах задача сводится к поиску одного корня по переменной \(R\): либо \(\sum_i \alpha_i(R)-\pi=0\), либо \(\sum_i \alpha_i(R)-2\alpha_{\max}(R)=0\).
Для стороны длины \(\ell_i\) площадь равнобедренного треугольника, образованного центром окружности и соответствующей хордой, равна
$$A_i(R)=\frac{1}{2}R^2\sin\bigl(2\alpha_i(R)\bigr)=\frac{\ell_i}{4}\sqrt{4R^2-\ell_i^2}.$$
Следовательно, в случае только малых дуг
$$A_{\max}=\sum_i A_i(R).$$
В случае большой дуги вклад самой длинной стороны идёт с противоположной ориентацией, и площадь равна
$$A_{\max}=\left|\sum_i A_i(R)-2A_L(R)\right|.$$
Итак, для фиксированного \(n\)
$$\mathbb{E}_n=\sum_{(c_r)} P(c_0,c_1,c_2,\dots)\,A_{\max}(c_0,c_1,c_2,\dots),$$
а итоговый ответ есть \(S=\sum_{n=3}^{50}\mathbb{E}_n\).
Здесь \(E=n-3=1\), поэтому общее число упорядоченных исходов равно
$$\binom{2n-4}{n-1}=\binom{4}{3}=4.$$
Существует только одно мультимножество длин сторон: \(\{2,1,1,1\}\). Оно встречается во всех четырёх упорядочениях, значит его вероятность равна \(1\).
Самая длинная сторона имеет длину \(2\), следовательно минимально допустимый радиус равен \(R_0=1\). При этом радиусе
$$\alpha(2)=\arcsin(1)=\frac{\pi}{2},\qquad \alpha(1)=\arcsin\left(\frac{1}{2}\right)=\frac{\pi}{6},$$
и потому
$$\alpha(2)+3\alpha(1)=\frac{\pi}{2}+3\cdot\frac{\pi}{6}=\pi.$$
Значит, уравнение для малых дуг уже выполняется при \(R=1\). Максимальная площадь равна
$$A=\frac{2}{4}\sqrt{4-4}+3\cdot \frac{1}{4}\sqrt{4-1}=\frac{3\sqrt{3}}{4}\approx 1.299038,$$
и это совпадает с промежуточным контрольным значением в реализации.
Реализации на C++, Python и Java следуют одному и тому же математическому плану. Сначала заранее вычисляются логарифмы факториалов, чтобы устойчиво считать мультиномиальные вероятности и не сталкиваться с переполнением. Для каждого \(n\) реализация берёт \(E=n-3\) и рекурсивно перечисляет все разбиения числа \(E\); каждое разбиение напрямую задаёт одно мультимножество длин сторон.
Для каждого мультимножества реализация вычисляет логарифмический вес, переводит его в вероятность и определяет максимальную длину. Затем в точке \(R_0=\max \ell_i/2\) проверяется, существует ли решение в режиме малых дуг. После этого корень нужного уравнения сначала зажимается сверху и снизу расширением верхней границы до смены знака, а затем уточняется шагом Ньютона с подстраховкой методом бисекции.
Производная, используемая в шаге Ньютона, имеет вид
$$\alpha_i'(R)=-\frac{\ell_i}{R\sqrt{4R^2-\ell_i^2}}.$$
Поэтому одного прохода по кратностям сторон достаточно, чтобы получить и значение функции, и её производную. Когда \(R\) найден, реализация суммирует треугольные вклады всех хорд, при необходимости применяет поправку на большую дугу, умножает результат на вероятность мультимножества, накапливает \(\mathbb{E}_n\), а затем суммирует все значения от \(n=3\) до \(n=50\).
Для фиксированного \(n\) положим \(E=n-3\), а через \(p(E)\) обозначим число разбиений \(E\). Программа создаёт ровно одно состояние на каждое разбиение, то есть выполняет \(p(E)\) геометрических вычислений. Каждое вычисление делает константное число проходов по различным длинам сторон и выполняет поиск корня с ограниченным числом итераций, что даёт \(O(EI)\) работы на одно разбиение, где \(I\) — число итераций численного решателя.
Следовательно, временная сложность для одного \(n\) равна
$$O\bigl(p(E)\,E\,I\bigr),$$
а память составляет \(O(E)\) для хранения кратностей плюс небольшой \(O(n)\)-массив логарифмов факториалов. Поскольку в задаче требуется только \(n\le 50\), то \(E\le 47\), и такой полный взвешенный перебор вполне реалистичен.
لكل \(n\) بحيث \(3 \le n \le 50\)، نختار بالتساوي بين جميع الترتيبات المرتبة للأعداد الصحيحة الموجبة \((\ell_1,\dots,\ell_n)\) التي تحقق
$$\ell_1+\cdots+\ell_n=2n-3.$$
ولكل اختيار من هذا النوع نرمز بـ \(A_{\max}(\ell_1,\dots,\ell_n)\) إلى أكبر مساحة يمكن أن يحققها مضلع بسيط بهذه الأطوال بالضبط. لذلك، عند تثبيت \(n\)، تكون القيمة المتوقعة
$$\mathbb{E}_n=\frac{1}{\binom{2n-4}{n-1}}\sum_{\substack{\ell_1+\cdots+\ell_n=2n-3\\ \ell_i\ge 1}} A_{\max}(\ell_1,\dots,\ell_n),$$
والمطلوب في النهاية هو
$$S=\sum_{n=3}^{50}\mathbb{E}_n.$$
التعداد المباشر لكل الترتيبات المرتبة مكلف جدًا. لذلك تضغط الخوارزمية الحالات التي تشترك في نفس متعدد أطوال الأضلاع، وتحل مسألة هندسية واحدة لكل متعدد، ثم تزن النتيجة باحتمالها الصحيح.
يعتمد الحل على فكرتين أساسيتين: النموذج العشوائي يمكن وصفه بصيغة تراكيب عددية، ومع ثبات أطوال الأضلاع فإن المضلع ذا المساحة العظمى يكون مضلعًا دائريًا.
نكتب كل ضلع على الصورة
$$\ell_i=1+e_i,\qquad e_i\in\mathbb{Z}_{\ge 0},\qquad \sum_{i=1}^{n} e_i=n-3=:E.$$
وبذلك يصبح الاختيار العشوائي، عند تثبيت \(n\)، اختيارًا منتظمًا لتركيب مرتب للعدد \(E\) إلى \(n\) أجزاء غير سالبة. ومن مبدأ stars and bars يكون عدد الحالات الكلي
$$\binom{E+n-1}{n-1}=\binom{2n-4}{n-1}.$$
وهذه الصياغة تبين أيضًا أن كل عينة تستطيع تكوين مضلع فعلًا: أكبر ضلع ممكن هو \(1+E=n-2\)، بينما مجموع الأضلاع الأخرى وعددها \(n-1\) لا يقل عن \(n-1\)، وهو أكبر من ذلك الحد.
لكل \(r\ge 1\)، ليكن \(c_r\) عدد الأضلاع ذات الزيادة \(r\)، أي الأضلاع التي طولها \(r+1\). وليكن \(c_0\) عدد الأضلاع ذات الطول \(1\). عندئذ
$$\sum_{r\ge 1} r\,c_r=E,\qquad c_0=n-\sum_{r\ge 1} c_r.$$
المعطيات \((c_1,c_2,\dots)\) تمثل بالضبط partition للعدد \(E\)، ولهذا تعدد الخوارزمية partitions بدلًا من جميع الترتيبات المرتبة. بالنسبة إلى متعدد أطوال ثابت، فإن عدد الترتيبات الممكنة هو
$$\frac{n!}{c_0!\prod_{r\ge 1} c_r!},$$
ومن ثم يكون احتماله
$$P(c_0,c_1,c_2,\dots)=\frac{n!}{c_0!\prod_{r\ge 1} c_r!}\cdot \binom{2n-4}{n-1}^{-1}.$$
وهذا الضغط صحيح لأن المساحة العظمى لا تعتمد على ترتيب الأضلاع داخل العينة المرتبة، بل على متعدد الأطوال فقط.
عند تثبيت متعدد الأطوال، فإن المضلع الأعظمي مساحة يكون دائريًا. إذا كان نصف قطر الدائرة المحيطة هو \(R\)، فنعرّف لكل ضلع نصف الزاوية المركزية الصغرى الموافقة له بالصيغة
$$\alpha_i(R)=\arcsin\left(\frac{\ell_i}{2R}\right),\qquad R\ge \frac{\max_i \ell_i}{2}.$$
إذا كان مركز الدائرة داخل المضلع، فإن جميع الأضلاع تقابل أقواسًا صغرى، وعندها يكون مجموع الزوايا المركزية \(2\pi\)، أي
$$2\sum_i \alpha_i(R)=2\pi \qquad\Longleftrightarrow\qquad \sum_i \alpha_i(R)=\pi.$$
وبما أن كل \(\alpha_i(R)\) يتناقص عندما يزداد \(R\)، فإن وجود حل في حالة الأقواس الصغرى يكافئ تحقق الشرط عند أصغر نصف قطر مسموح \(R_0=\max_i \ell_i/2\):
$$\sum_i \alpha_i(R_0)\ge \pi.$$
إذا كان \(\sum_i \alpha_i(R_0)<\pi\)، فهذا يعني أن البنية المثلى لا يمكن أن تجعل جميع الأضلاع على أقواس صغرى. في هذه الحالة يستخدم الضلع الأطول الوحيد قوسًا كبيرًا، بينما تبقى بقية الأضلاع على أقواس صغرى.
إذا رمزنا بنصف الزاوية الموافقة لذلك الضلع الأطول إلى \(\alpha_{\max}(R)\)، فإن شرط مجموع الزوايا يصبح
$$2\sum_{i\ne \max}\alpha_i(R)+\bigl(2\pi-2\alpha_{\max}(R)\bigr)=2\pi,$$
وهو يكافئ
$$\sum_i \alpha_i(R)=2\alpha_{\max}(R).$$
وبذلك تختزل المسألة الهندسية في الحالتين إلى إيجاد جذر لمعادلة عددية واحدة في \(R\): إما \(\sum_i \alpha_i(R)-\pi=0\)، أو \(\sum_i \alpha_i(R)-2\alpha_{\max}(R)=0\).
بالنسبة إلى ضلع طوله \(\ell_i\)، فإن مساحة المثلث متساوي الساقين المؤلف من المركز والوتر هي
$$A_i(R)=\frac{1}{2}R^2\sin\bigl(2\alpha_i(R)\bigr)=\frac{\ell_i}{4}\sqrt{4R^2-\ell_i^2}.$$
ومن ثم، في حالة الأقواس الصغرى فقط، نحصل على
$$A_{\max}=\sum_i A_i(R).$$
أما في حالة القوس الكبير فإن مساهمة الضلع الأطول تدخل بإشارة معاكسة، ولذلك تصبح المساحة
$$A_{\max}=\left|\sum_i A_i(R)-2A_L(R)\right|.$$
وبالتالي، عندما يكون \(n\) ثابتًا، يمكن كتابة
$$\mathbb{E}_n=\sum_{(c_r)} P(c_0,c_1,c_2,\dots)\,A_{\max}(c_0,c_1,c_2,\dots),$$
أما الجواب النهائي فهو \(S=\sum_{n=3}^{50}\mathbb{E}_n\).
هنا \(E=n-3=1\)، ولذلك يكون عدد الحالات المرتبة الكلي
$$\binom{2n-4}{n-1}=\binom{4}{3}=4.$$
ولا يوجد سوى متعدد أطوال واحد هو \(\{2,1,1,1\}\)، ويظهر في الترتيبات الأربعة جميعًا، لذا فاحتماله يساوي \(1\).
أطول ضلع طوله \(2\)، ومن ثم فإن أصغر نصف قطر مسموح هو \(R_0=1\). عند هذا النصف من القطر نحصل على
$$\alpha(2)=\arcsin(1)=\frac{\pi}{2},\qquad \alpha(1)=\arcsin\left(\frac{1}{2}\right)=\frac{\pi}{6},$$
ومن ثم
$$\alpha(2)+3\alpha(1)=\frac{\pi}{2}+3\cdot\frac{\pi}{6}=\pi.$$
أي أن معادلة الأقواس الصغرى تتحقق أصلًا عند \(R=1\). وتكون المساحة العظمى
$$A=\frac{2}{4}\sqrt{4-4}+3\cdot \frac{1}{4}\sqrt{4-1}=\frac{3\sqrt{3}}{4}\approx 1.299038,$$
وهو تمامًا نفس مقدار التحقق الوسيط الذي تنتجه الخوارزمية.
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها. تبدأ الشيفرة بحساب لوغاريتمات المضروبات مسبقًا، وهذا يسمح بحساب الاحتمالات متعددة الحدود بطريقة مستقرة وبدون تجاوزات عددية. لكل \(n\)، تضبط الشيفرة \(E=n-3\)، ثم تعدد جميع partitions للعدد \(E\) بطريقة تكرارية؛ وكل partition تمثل مباشرةً متعدد أطوال واحدًا.
لكل متعدد أطوال، تحسب الشيفرة الوزن اللوغاريتمي، ثم تحوله إلى احتمال، وتحدد الضلع الأطول. بعد ذلك تختبر نصف القطر الأدنى المسموح \(R_0=\max \ell_i/2\) لتقرير ما إذا كانت معادلة الأقواس الصغرى قابلة للحل. ثم تحيط الجذر الصحيح بمجال عبر توسيع الحد العلوي حتى يحدث تغير في الإشارة، وبعدها تستعمل خطوة Newton محمية بطريقة التنصيف.
المشتقة المستخدمة في تحديث Newton هي
$$\alpha_i'(R)=-\frac{\ell_i}{R\sqrt{4R^2-\ell_i^2}}.$$
ولهذا يكفي المرور مرة واحدة على تعددات الأضلاع للحصول على قيمة الدالة ومشتقتها معًا. بعد معرفة \(R\)، تجمع الشيفرة مساهمات المثلثات الناتجة عن جميع الأوتار، وتطبق تصحيح إشارة الضلع الأطول في حالة القوس الكبير عند الحاجة، ثم تضرب بالاحتمال المناسب، وتراكم \(\mathbb{E}_n\)، وأخيرًا تجمع كل القيم من \(n=3\) حتى \(n=50\).
عند تثبيت \(n\)، لنكتب \(E=n-3\)، ولتكن \(p(E)\) هي دالة عدد partitions للعدد \(E\). تولد الشيفرة حالة واحدة بالضبط لكل partition، أي أن عدد التقييمات الهندسية لذلك \(n\) يساوي \(p(E)\). وكل تقييم يمسح الأطوال المختلفة عددًا ثابتًا من المرات ويجري عملية إيجاد جذر بعدد محدود من التكرارات، فيكون العمل لكل partition من الرتبة \(O(EI)\)، حيث \(I\) هو عدد تكرارات المحلل العددي.
إذًا فإن الكلفة الزمنية لـ \(n\) ثابت هي
$$O\bigl(p(E)\,E\,I\bigr),$$
أما الذاكرة فهي \(O(E)\) لبيانات التعددات، إضافة إلى جدول صغير حجمه \(O(n)\) للوغاريتمات المضروبية. وبما أن المسألة لا تحتاج إلا إلى \(n\le 50\)، فإن \(E\le 47\)، ولذلك فإن هذا التعداد الموزون الكامل عملي تمامًا.