Project Euler Problem 863
Using only a six-sided fair dice and a five-sided fair dice, we would like to emulate an n-sided fair dice.
Solution
Answer: 3862.871397
Let the process currently have $a$ equiprobable unresolved states (initially $a=1$).
If we roll a die with $d\in{5,6}$ faces, the number of equiprobable outcomes becomes $ad$.
To emulate an $n$-sided die fairly:
- We may immediately assign as many outcomes as possible to the $n$ target values.
- Write
$$ad = qn + r,\qquad 0\le r<n.$$
- We can accept $qn$ outcomes (uniformly distributed over $1,\dots,n$) and continue only on the leftover $r$ outcomes.
If $F(a)$ is the optimal expected additional number of rolls needed starting from $a$ unresolved equiprobable states, then
$$F(a) = \min_{d\in{5,6}} \left( 1 + \frac{r}{ad}F(r) \right), \qquad r=(ad)\bmod n.$$
Why this is correct:
- The current roll always costs $1$.
- With probability $qn/(ad)$, we finish immediately.
- With probability $r/(ad)$, we recurse on $r$ unresolved states.
Boundary condition:
$$F(0)=0.$$
Then
$$R(n)=F(1), \qquad S(n)=\sum_{k=2}^n R(k).$$
This exactly reproduces the examples:
- $R(8)=2.083333333\ldots$
- $R(28)=2.142476190\ldots$
- $S(30)=56.054622093\ldots$
matching the statement.
A direct dynamic-programming/value-iteration implementation for each $n\le 1000$ gives
$$S(1000)=3862.871396558\ldots$$
Rounded to 6 decimal places:
Answer: 3862.871397