Detailed mathematical approach

Problem Summary

There are \(n\) chairs arranged in a circle. People sit down one after another, and each step chooses uniformly among the chairs that are still legal: a legal chair is unoccupied and not adjacent to an occupied chair. The process stops when no legal chair remains. The quantity of interest is the expected fraction of chairs that stay empty at the end.

The implementations verify the small checkpoints

$E(4)=\frac12,\qquad E(6)=\frac59,$

and then evaluate the actual target \(n=10^{18}\). A direct state-space analysis is hopeless, so the solution rewrites the process in terms of an expectation on a path and then solves that expectation in closed form.

Mathematical Approach

Let \(C(n)\) be the expected number of occupied chairs when the process runs on a cycle of length \(n\), and let \(E(n)\) be the expected empty-chair fraction:

$E(n)=1-\frac{C(n)}{n}.$

The core idea is that after the first occupied chair is chosen on the cycle, the remaining legal chairs form a simple path. That reduces the random process to a one-dimensional recurrence.

Step 1: Reduce the Cycle to a Path

Define \(P(m)\) as the expected number of occupied chairs produced by the same seating rule on a path of \(m\) chairs.

On a cycle of length \(n\), the first occupied chair contributes \(1\). Its two neighbors can never be occupied, so the remaining legal region is a path of length \(n-3\). Therefore, for \(n\ge 3\),

$C(n)=1+P(n-3).$

Hence the desired empty fraction is

$E(n)=1-\frac{1+P(n-3)}{n}.$

The small cases are consistent with this picture: \(E(1)=0\), \(E(2)=\frac12\), and \(E(3)=\frac23\).

Step 2: Recurrence for the Path Expectation

Now consider a path of \(m\) chairs. Suppose the first occupied chair is the \(j\)-th chair, where \(1\le j\le m\). Then chairs \(j-1\), \(j\), and \(j+1\) are no longer usable, so the process splits into two independent smaller paths:

$j-2,\qquad m-j-1.$

Taking expectations and averaging uniformly over the first choice gives

$P(m)=1+\frac{1}{m}\sum_{j=1}^{m}\bigl(P(j-2)+P(m-j-1)\bigr).$

Using symmetry, both sums are the same, so this simplifies to

$P(m)=1+\frac{2}{m}\sum_{r=0}^{m-2}P(r),\qquad P(0)=0.$

This is the main recurrence behind the exact formula.

Step 3: Solve the Recurrence with a Generating Function

Introduce the ordinary generating function

$F(x)=\sum_{m\ge 0}P(m)x^m.$

Multiply the recurrence by \(m x^{m-1}\) and sum over \(m\ge 1\). The left side becomes \(F'(x)\). The right side becomes

$\sum_{m\ge 1}m x^{m-1}=\frac{1}{(1-x)^2},$

and

$\sum_{m\ge 1}\sum_{r=0}^{m-2}P(r)x^{m-1}=\frac{xF(x)}{1-x}.$

Therefore \(F\) satisfies the linear differential equation

$F'(x)=\frac{1}{(1-x)^2}+\frac{2x}{1-x}F(x),\qquad F(0)=0.$

Solving it gives the exact generating function

$F(x)=\frac{1-e^{-2x}}{2(1-x)^2}.$

Step 4: Extract the Coefficient Formula

Write

$e^{-2x}=\sum_{k\ge 0}\frac{(-2)^k}{k!}x^k,$

and define the alternating partial sums

$S_m=\sum_{k=0}^{m}\frac{(-2)^k}{k!}.$

From

$F(x)=\frac{1}{2(1-x)^2}-\frac{e^{-2x}}{2(1-x)^2},$

the coefficient of \(x^m\) is

$P(m)=\frac{m+1}{2}-\frac12\sum_{k=0}^{m}(m-k+1)\frac{(-2)^k}{k!}.$

Using

$\sum_{k=0}^{m}k\frac{(-2)^k}{k!}=-2\sum_{k=0}^{m-1}\frac{(-2)^k}{k!}=-2S_{m-1},$

this becomes

$\boxed{P(m)=\frac{m+1}{2}-\frac{m+1}{2}S_m-S_{m-1}.}$

This is exactly the finite-\(n\) formula used by the exact implementation.

Step 5: Convert Back to the Cycle and Take the Limit

Substituting \(m=n-3\) into the cycle relation yields, for \(n\ge 4\),

$E(n)=1-\frac{1+P(n-3)}{n}.$

Because \(S_m\to e^{-2}\) as \(m\to\infty\), we obtain

$P(m)=\frac{m+1}{2}\bigl(1-e^{-2}\bigr)-e^{-2}+o(1).$

Hence

$\lim_{n\to\infty}E(n)=1-\frac{1}{2}\bigl(1-e^{-2}\bigr)=\boxed{\frac{1+e^{-2}}{2}}.$

This limit is the value needed for the huge target \(n=10^{18}\).

Worked Example: \(n=6\)

For a cycle of length \(6\), the first occupied chair leaves a path of length \(3\). We compute \(P(3)\) from the recurrence.

First, \(P(0)=0\), \(P(1)=1\), and \(P(2)=1\). Then

$P(3)=1+\frac{2}{3}\bigl(P(0)+P(1)\bigr)=1+\frac{2}{3}=\frac{5}{3}.$

So the expected number of occupied chairs on the cycle is

$C(6)=1+P(3)=1+\frac{5}{3}=\frac{8}{3}.$

Therefore the expected empty fraction is

$E(6)=1-\frac{C(6)}{6}=1-\frac{8/3}{6}=1-\frac49=\frac59,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations are built around the closed form above. The exact evaluation only needs the alternating partial sums \(S_m\), so the terms are generated iteratively by

$t_0=1,\qquad t_k=t_{k-1}\cdot\frac{-2}{k},\qquad S_m=\sum_{k=0}^{m}t_k.$

This avoids factorial overflow and keeps the computation in constant memory.

The C++ implementation handles the small cases explicitly, evaluates the exact finite-\(n\) formula for moderate \(n\), checks the known values \(E(4)=\frac12\) and \(E(6)=\frac59\), and then switches to the limit \(\frac{1+e^{-2}}{2}\) once \(n\) is large enough that the truncated-tail error is far below the printed precision.

The Python and Java implementations target the actual Euler input directly. Since that input is enormous, they compute the limiting constant immediately and print it to 14 decimal places.

Complexity Analysis

For the exact finite-\(n\) evaluation, computing \(S_m\) up to \(m=n-3\) takes \(O(n)\) time and \(O(1)\) memory, because only the current series term and running sum are stored. For the huge target value, the asymptotic formula is used directly, so the runtime is \(O(1)\) and the memory usage remains \(O(1)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=469
2. Exponential function and series: Wikipedia - Exponential function
3. Generating function: Wikipedia - Generating function
4. Linearity of expectation: Wikipedia - Expected value