Project Euler Problem 898
Claire Voyant is a teacher playing a game with a class of students.
Solution
Answer: 0.9861343531
Let $H$ be the event that the coin landed heads, and let the $i$-th student lie with probability $p_i$.
If the students’ reports are $r_1,\dots,r_n$, then Claire should use the likelihood ratio
$$\Lambda=\frac{\Pr(r_1,\dots,r_n\mid H)} {\Pr(r_1,\dots,r_n\mid T)}.$$
The optimal strategy is:
- guess Heads if $\Lambda>1$,
- guess Tails if $\Lambda<1$,
- either choice if $\Lambda=1$.
Hence the optimal success probability is
$$P(\Lambda>1)+\frac12 P(\Lambda=1),$$
computed under the assumption that the true outcome is Heads.
For a student with lie probability $p$,
- reporting Heads contributes a factor $\frac{1-p}{p}$,
- reporting Tails contributes a factor $\frac{p}{1-p}$.
The probabilities are $25%,26%,\dots,75%$.
The $50%$ student contributes nothing, and the remaining students naturally pair as
$$(p,1-p).$$
For each pair, the likelihood-ratio contribution becomes one of
$$\left(\frac{1-p}{p}\right)^2,\quad 1,\quad \left(\frac{p}{1-p}\right)^2$$
with probabilities
$$(1-p)^2,\quad 2p(1-p),\quad p^2.$$
There are only $25$ such independent paired contributions, so a meet-in-the-middle computation over the $3^{25}$ states gives the exact optimal success probability:
$$0.986134353087556\ldots$$
Rounded to $10$ digits after the decimal point:
Answer: 0.9861343531