Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Reparameterize the Random Side Lengths

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\).

Step 2: Compress Ordered Tuples to Side-Length Multisets

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.

Step 3: Reduce the Geometry to One Circumradius Equation

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.$

Step 4: Handle the Major-Arc Regime When the Minor Equation Fails

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\).

Step 5: Convert the Radius into an Area

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\).

Worked Example: \(n=4\)

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.

How the Code Works

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\).

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=564
2. Cyclic polygon: Wikipedia — Cyclic polygon
3. Integer composition: Wikipedia — Composition (combinatorics)
4. Brahmagupta's formula: Wikipedia — Brahmagupta's formula
5. Newton's method: Wikipedia — Newton's method
6. Bisection method: Wikipedia — Bisection method