Project Euler Problem 503
Alice is playing a game with n cards numbered 1 to n.
Solution
Answer: 3.8694550145
Let $V_s$ denote the optimal expected normalized score after the $s$-th card has been drawn (so $s$ cards have been seen), where we divide all expectations by $n+1$.
If the current card has relative rank $r$ among the $s$ seen cards, then:
- stopping gives expected normalized score
$$\frac{r}{s+1},$$
because the expected value of the $r$-th smallest element among $s$ sampled cards from ${1,\dots,n}$ is
$$\frac{r(n+1)}{s+1}.$$
- continuing gives expected normalized score $V_{s+1}$.
Hence Alice stops iff
$$\frac{r}{s+1} \le V_{s+1}.$$
Since $r$ is uniformly distributed over $1,\dots,s$,
$$V_s = \frac1s \sum_{r=1}^{s} \min!\left(\frac{r}{s+1},,V_{s+1}\right).$$
Boundary condition:
$$V_n=\frac12,$$
because with one forced final choice the expected rank is $(n+1)/2$.
Define
$$k=\left\lfloor (s+1)V_{s+1}\right\rfloor .$$
Then
$$V_s = \frac{ \frac{k(k+1)}{2(s+1)} + (s-k)V_{s+1} }{s}.$$
Finally,
$$F(n)=(n+1)V_1.$$
Running the recurrence for $n=10^6$ gives:
$$F(10^6)=3.869455014481\ldots$$
Rounded to 10 digits after the decimal point:
Answer: 3.8694550145