Detailed mathematical approach

Problem Summary

We begin with two flocks, one white and one black, each containing \(n\) sheep. Every sheep is equally likely to bleat next. If a white sheep bleats, one black sheep crosses over and becomes white, so \((w,b)\mapsto (w+1,b-1)\). If a black sheep bleats, one white sheep crosses over and becomes black, so \((w,b)\mapsto (w-1,b+1)\). After this colour change, Peredur may remove any number of white sheep. The goal is to maximize the expected final number of black sheep, denoted \(E(n)\), starting from the balanced position \((n,n)\).

The published solver computes this expectation to fixed decimal precision but, as elsewhere on the site, intentionally does not reveal the final Project Euler value.

Mathematical Approach

Let \(V(w,b)\) be the optimal expected final number of black sheep when the current state contains \(w\) white and \(b\) black sheep and Peredur is allowed to prune white sheep immediately.

Terminal States

If no white sheep remain, the process is over and all remaining sheep are black, so

$V(0,b)=b.$

If no black sheep remain, the terminal payoff is zero:

$V(w,0)=0.$

These boundary values anchor the entire dynamic program.

Bellman Equation

Suppose Peredur keeps exactly \(k\) white sheep, with \(1\le k\le w\). The next bleat is white with probability \(\frac{k}{k+b}\), leading to \((k+1,b-1)\), and black with probability \(\frac{b}{k+b}\), leading to \((k-1,b+1)\). Hence the one-step continuation value is

$C(k,b)=\frac{k}{k+b}V(k+1,b-1)+\frac{b}{k+b}V(k-1,b+1).$

If he removes all white sheep (\(k=0\)), the game stops immediately and the payoff is simply \(b\). Therefore the Bellman optimization is

$V(w,b)=\max\!\left(b,\ \max_{1\le k\le w} C(k,b)\right).$

This is a stochastic control problem: the decision is how many white sheep to keep, and the randomness comes from the next bleat.

Shape of the Optimal Policy

The fast solver relies on the policy

$k^*(w,b)=\min(w,b-1),$

which is independently checked by the exact solver on all small states used in the C++ checkpoints. In words, once white sheep are at least as numerous as black sheep, it is never beneficial to keep them above \(b-1\).

The intuition is straightforward: only black sheep contribute to the final payoff, while extra white sheep increase the chance of a white bleat, and a white bleat converts one black sheep into a white sheep. So excess white sheep are pure risk and can be removed without sacrificing upside.

Layering by the Fixed Total \(s=w+b\)

Between bleats no sheep are created; colours only swap. This makes the total

$s=w+b$

a natural layer index. Define

$U_s(w)=V(w,s-w).$

If \(w\le b-1\), equivalently \(1\le w\le t\) with

$t=\left\lfloor\frac{s-1}{2}\right\rfloor,$

then no immediate pruning occurs, and the Bellman equation reduces to the continuation recurrence

$U_s(w)=\frac{w}{s}U_s(w+1)+\frac{s-w}{s}U_s(w-1).$

If \(w\ge b\), the optimal policy removes white sheep until the state leaves that region. One immediate pruning step gives

$U_s(w)=U_{s-1}(w-1),\qquad w\ge t+1.$

Applying this relation repeatedly is exactly the same as capping white sheep to \(b-1\).

Tridiagonal Linear System

For a fixed layer \(s\), the unknown continuation values are \(U_s(1),U_s(2),\dots,U_s(t)\). Rearranging the recurrence gives

$-\frac{s-w}{s}U_s(w-1)+U_s(w)-\frac{w}{s}U_s(w+1)=0,\qquad 1\le w\le t.$

The left boundary is known exactly:

$U_s(0)=V(0,s)=s.$

The right boundary is inherited from the pruning region:

$U_s(t+1)=U_{s-1}(t).$

So each layer becomes a tridiagonal linear system, which the code solves in \(O(s)\) time by forward elimination and back substitution.

Recovering \(E(n)\) from the Balanced Start

The initial position is \((n,n)\), but Peredur may prune only after the first bleat and crossover. By symmetry, the first bleat is white or black with probability \(\frac12\). Thus

$E(n)=\frac{V(n+1,n-1)+V(n-1,n+1)}{2}=\frac{U_{2n}(n+1)+U_{2n}(n-1)}{2}.$

This is why the implementation computes the full layer \(s=2n\) and then averages the two neighboring states around the diagonal start.

Worked Example: \(n=1\)

With one white and one black sheep, the first bleat already determines the outcome. If the white sheep bleats, the state becomes \((2,0)\), so the final number of black sheep is \(0\). If the black sheep bleats, the state becomes \((0,2)\), so the final number of black sheep is \(2\). Therefore

$E(1)=\frac{0+2}{2}=1.$

The code also checks the published benchmark \(E(5)=6.871346\) (rounded to six decimals) as a checkpoint for the fast recurrence.

How the Code Works

The arrays prev and cur store the values of \(U_{s-1}\) and \(U_s\). For each layer \(s\), the cap region \(w\ge t+1\) is filled immediately by cur[w] = prev[w-1], implementing the pruning rule.

The continuation region \(1\le w\le t\) is then solved as a tridiagonal system using temporary arrays for the diagonal, superdiagonal, and right-hand side coefficients. After the final layer \(s=2n\) is built, the answer is returned as

$\frac{\texttt{prev}[n-1]+\texttt{prev}[n+1]}{2}.$

In the C++ version, an exact small-state solver is additionally used to verify the cap policy and to compare the fast method against exact values on sample inputs.

Complexity Analysis

Layer \(s\) contains \(O(s)\) relevant states and is solved in \(O(s)\) time. Summing over \(s=1,2,\dots,2n\) gives

$O(1+2+\cdots+2n)=O(n^2).$

Only the current layer, the previous layer, and a few temporary tridiagonal arrays are stored, so the memory usage is \(O(n)\).

Further Reading

1. Problem page: https://projecteuler.net/problem=339
2. Bellman equations / dynamic programming: https://en.wikipedia.org/wiki/Dynamic_programming
3. Tridiagonal systems (Thomas algorithm): https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm