Peredur Fab Efrawg

“And he came towards a valley, through which ran a river; and the borders of the valley were wooded, and on each side of the river were level meadows. And on one side of the river he saw a flock of white sheep, and on the other a flock of black sheep. And whenever one of the white sheep bleated, one of the black sheep would cross over and become white; and when one of the black sheep bleated, one of the white sheep would cross over and become black.”en.wikisource.org

Initially each flock consists of $n$ sheep. Each sheep (regardless of colour) is equally likely to be the next sheep to bleat. After a sheep has bleated and a sheep from the other flock has crossed over, Peredur may remove a number of white sheep in order to maximize the expected final number of black sheep. Let $E(n)$ be the expected final number of black sheep if Peredur uses an optimal strategy.

You are given that $E(5) = 6.871346$ rounded to $6$ places behind the decimal point.
Find $E(10\,000)$ and give your answer rounded to $6$ places behind the decimal point.

This question is a problem from the Project Euler(Problem 319). Peredur fab Efrawg. It’s a difficult problem that makes use of expected values with optimal strategies, and it’s better solved computationally.

Here’s a quick and simplified explanation:

Let’s denote $E_X(Y)$ as the expected number of black sheep after Peredur removed $X$ white sheep when there are $Y$ white sheep bleating.

Then we can state following:

$E_0(1)=0.5*(E_0(1)+E_1(1))=\frac{1}{2}$

$E_0(2)=\frac{1}{3}*(E_0(2)+E_1(2)+E_2(2))=\frac{2}{3}$

Continuing this way, you compute a couple of more steps, and you will realize that:

$E_0(X)=\frac{X}{X+1}$

Using symmetry, each step could either increase the count of white or black sheep. Thus, our recursion can work as following:

$E(X,Y)=\frac{X}{X+Y} * E(X+1,Y-1) + \frac{Y}{X+Y} * (1+E(X,Y-1))$ where $E(X,0)=X$.

Using the above recurrence relation, we can start with $X$ = 10000 and $Y$ = 10000, and keep updating as per the recurrence until we reach $Y$ = 0. This would give us the value of $E(10\,000)$ to any required number of decimal places.

Python code to solve this problem:

,,,,,,,,,,

def calculate_expected(n):
dp = [0] * (n + 1)
for i in range(2, n + 1):
for j in range(1, i):
dp[i] += (dp[j] + dp[i – j] + 1) / (i – 1)
return dp[n]

def main():
n = 10000
result = calculate_expected(n)
print(“{:.6f}”.format(result))

if __name__ == “__main__”:
main()

More Answers:

Maximix Arrangements
Totient Stairstep Sequences
Cutting Rectangular Grid Paper