Project Euler Problem 640

Solution

Answer: 50.317928

Let a state be the set of face-down cards. There are $2^{12}=4096$ states, so this is a finite Markov decision process.

Define:

$S$: current subset of face-down cards.
$E(S)$: minimum expected remaining number of turns to reach the all-face-down state.
Goal state $G={1,\dots,12}$, with $E(G)=0$.

On each turn Bob rolls $(x,y)\in{1,\dots,6}^2$, each of the 36 outcomes equally likely. After seeing the roll, he may toggle one of:

$$x,\qquad y,\qquad x+y.$$

If toggling card $k$, the new state is:

$$S' = S \triangle {k}$$

(where $\triangle$ is symmetric difference / bit flip).

By optimal play, after observing the roll Bob chooses the action minimizing future expectation, so Bellman optimality gives:

$$E(S) = 1 + \frac1{36} \sum_{x=1}^{6} \sum_{y=1}^{6} \min \Bigl( E(S\triangle{x}), E(S\triangle{y}), E(S\triangle{x+y}) \Bigr)$$

for every non-goal state $S$.

This system has 4096 unknowns. Since the Bellman operator is a contraction, value iteration converges rapidly.

To verify correctness, applying the same method to Alice’s 4-card coin game gives:

$$5.673650793650768$$

which matches the problem statement ($\approx 5.673651$).

Running the computation for Bob’s 12-card game gives:

$$E(\varnothing)=50.31792785864575$$

Rounded to 6 decimal places:

Answer: 50.317928