Project Euler Problem 469

Solution

Answer: 0.56766764161831

Let $M_N$ be the number of occupied chairs when the process stops on a cycle of $N$ chairs. Then

$$E(N)=\mathbb E!\left[\frac{N-M_N}{N}\right] =1-\frac{\mathbb E[M_N]}{N}.$$

So the task is to compute the asymptotic expected occupied density.

---

1. Mathematical analysis

Step 1: Convert the circular problem into a linear one

It is easier to first study a line of $n$ chairs.

Define:

$$a_n=\text{expected number of occupied chairs on a line of } n \text{ chairs}.$$

When the first knight chooses chair $k$ ($1\le k\le n$):

• chair $k$ becomes occupied,
• chairs $k-1$ and $k+1$ become forbidden,
• the remaining available chairs split into two independent subproblems:

$$k-2 \quad\text{and}\quad n-k-1.$$

Therefore,

$$a_n = 1+\frac1n\sum_{k=1}^n\left(a_{k-2}+a_{n-k-1}\right),$$

with $a_m=0$ for $m<0$.

By symmetry,

$$a_n = 1+\frac{2}{n}\sum_{i=0}^{n-2} a_i. \tag{1}$$

Initial values:

$$a_0=0,\qquad a_1=1.$$

---

Step 2: Generating function

Define

$$A(x)=\sum_{n\ge0} a_n x^n.$$

From (1),

$$n a_n = n+2\sum_{i=0}^{n-2} a_i.$$

Multiply by $x^n$ and sum over $n\ge2$:

$$\sum_{n\ge2} n a_n x^n = \sum_{n\ge2} n x^n + 2\sum_{n\ge2}\sum_{i=0}^{n-2} a_i x^n.$$

Using standard generating-function identities:

$$xA'(x)-x = \frac{x}{(1-x)^2}-x + \frac{2x^2}{1-x}A(x).$$

Hence

$$A'(x)-\frac{2x}{1-x}A(x)=\frac{1}{(1-x)^2}.$$

Solve this linear ODE.

The integrating factor is

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

Thus,

$$\frac{d}{dx}!\left(\mu(x)A(x)\right)=e^{2x}.$$

Integrating:

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

Therefore,

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

---

Step 3: Extract the asymptotic density

Near $x=1$,

$$A(x)\sim \frac{1-e^{-2}}{2(1-x)^2}.$$

Since

$$[x^n]\frac1{(1-x)^2}=n+1,$$

we get

$$a_n \sim \frac{1-e^{-2}}{2},n.$$

So the asymptotic occupied fraction on a long line is

$$\frac{1-e^{-2}}{2}.$$

---

Step 4: Return to the circle

For a cycle of $N$ chairs:

• the first occupied chair blocks itself and its two neighbors,
• the remaining chairs form a line of length $N-3$.

Hence

$$\mathbb E[M_N]=1+a_{N-3}.$$

Therefore,

$$E(N) = 1-\frac{1+a_{N-3}}{N}.$$

As $N\to\infty$,

$$\frac{1+a_{N-3}}{N} \to \frac{1-e^{-2}}{2}.$$

So

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

Since $10^{18}$ is enormous, $E(10^{18})$ equals this limit to far more than 14 decimal places.

---

2. Python implementation

from decimal import Decimal, getcontext

# high precision arithmetic
getcontext().prec = 50

# compute limiting value
ans = (Decimal(1) + (-Decimal(2)).exp()) / Decimal(2)

# print to 14 decimal places
print(f"{ans:.14f}")

---

3. Code walkthrough

from decimal import Decimal, getcontext

Imports arbitrary-precision decimal arithmetic.

---

getcontext().prec = 50

Sets precision high enough to avoid rounding issues.

---

ans = (Decimal(1) + (-Decimal(2)).exp()) / Decimal(2)

Computes

$$\frac{1+e^{-2}}{2}.$$

---

print(f"{ans:.14f}")

Formats the answer to exactly 14 decimal places.

---

4. Small-case verification

The problem states:

$$E(4)=\frac12.$$

Indeed:

• exactly 2 chairs become occupied,
• so 2 remain empty,

$$E(4)=\frac24=\frac12.$$

Also:

$$E(6)=\frac59,$$

which matches the recurrence computation.

The limiting value

$$\frac{1+e^{-2}}{2}\approx 0.5676676$$

is plausible:

• more than half the chairs remain empty,
• because every occupied chair forces neighboring vacancies.

---

Answer: 0.56766764161831