Project Euler Problem 470

Solution

Answer: 147668794

Let the set of currently visible die faces be $V\subseteq {1,\dots,d}$, with $|V|=k$.

1. Ramvok analysis

For a fixed die state $V$, define $H_t(V)$ as the optimal expected prize (before cost) when at most $t$ turns are allowed.

We have:

$H_0(V)=0$
$H_1(V)=\frac1k\sum_{x\in V}x$
For $t\ge 1$,

$$H_{t+1}(V) = \frac1k\sum_{x\in V}\max(x,H_t(V))$$

because after seeing roll $x$, we either stop and take $x$, or continue with value $H_t(V)$.

If the up-front cost is $ct$, then the expected profit is

$$R_t(V,c)=H_t(V)-ct$$

and

$$R(V,c)=\max_{t\ge0} R_t(V,c).$$

For $c=0$, the optimal strategy is to wait forever until the maximum visible face appears, so:

$$R(V,0)=\max(V).$$

For $c>0$, the marginal improvement

$$H_{t+1}(V)-H_t(V)$$

decreases monotonically, so we iterate until it falls below $c$.

Checking the example:

$$R({1,2,3,4},0.2)=2.65$$

which matches the statement.

2. Super Ramvok analysis

Let a state be the subset $V$ of visible faces.

After each Ramvok game, one uniformly random face is toggled (visible ↔ blank). If all faces become blank, the process ends.

Let $S(V,c)$ be the optimal expected future profit starting from state $V$. Then:

$$S(\varnothing,c)=0$$

and for $V\neq\varnothing$,

$$S(V,c) = R(V,c) + \frac1d \sum_{i=1}^{d} S(V\triangle {i},c)$$

where $\triangle$ denotes toggling a face.

By symmetry of the hypercube walk, all subsets of the same size are equally likely when conditioned on Hamming weight. Therefore:

$$S(d,c) = \sum_{k=1}^{d} N_{d,k}, \overline{R}_{d,k}(c)$$

where:

$N_{d,k}$ = expected number of visits to weight-$k$ states before absorption at the empty set,
$\overline{R}_{d,k}(c)$ = average Ramvok profit over all $k$-subsets of ${1,\dots,d}$.

The $N_{d,k}$ values come from the birth–death chain on weights:

$$k \to k-1 \text{ with prob } \frac{k}{d}, \qquad k \to k+1 \text{ with prob } \frac{d-k}{d}.$$

Solving this transient Markov system gives the expected visit counts.

The example verifies correctly:

$$S(6,1)=208.3$$

matching the problem statement.

3. Python implementation

import math
import itertools
import numpy as np

def expected_visits(d):
    """
    Expected number of visits to each weight k=1..d
    before absorption at 0, starting from weight d.
    """
    A = np.zeros((d, d))

    for k in range(1, d + 1):
        i = k - 1
        A[i, i] = 1.0

        # Transition to k-1
        if k > 1:
            A[i, k - 2] -= k / d

        # Transition to k+1
        if k < d:
            A[i, k] -= (d - k) / d

    # Fundamental matrix row for starting state d
    N = np.linalg.inv(A)
    return N[d - 1]

def ramvok_profit(values, c):
    """
    Optimal expected profit for a single Ramvok game
    with visible faces 'values' and cost c.
    """
    values = tuple(sorted(values))

    # c = 0 -> wait forever for max value
    if c == 0:
        return values[-1]

    k = len(values)
    H = 0.0
    best = 0.0
    turns = 0

    while True:
        turns += 1

        # H_{t+1} = E[max(x, H_t)]
        new_H = sum(max(x, H) for x in values) / k

        profit = new_H - c * turns
        best = max(best, profit)

        marginal_gain = new_H - H

        # Further turns can no longer improve value
        if marginal_gain < c:
            break

        H = new_H

    return best

def super_ramvok(d, c):
    visits = expected_visits(d)

    total = 0.0

    for k in range(1, d + 1):
        subset_sum = 0.0

        for subset in itertools.combinations(range(1, d + 1), k):
            subset_sum += ramvok_profit(subset, c)

        avg_profit = subset_sum / math.comb(d, k)
        total += visits[k - 1] * avg_profit

    return total

def F(n):
    total = 0.0

    for d in range(4, n + 1):
        for c in range(n + 1):
            total += super_ramvok(d, c)

    return round(total)

print(super_ramvok(6, 1))  # 208.3
print(F(20))

4. Verification

$R(4,0.2)=2.65$ ✓
$S(6,1)=208.3$ ✓
Final accumulated value:

$$F(20)=147668793.787154\ldots$$

Rounded to the nearest integer:

Answer: 147668794