Optimal Strategies in the All-Heads Coin Game

In the all-heads coin game a player starts with $n$ coins, each showing heads with
probability $p$; each round all remaining coins are flipped, the player must set aside at
least one head (losing if none shows), and wins once all coins are set aside. Determine
optimal strategies and the winning probability $w_{n,p}$. Resolved: for $p=\tfrac12$ every
strategy achieves $w_{n,1/2}=\tfrac12$; for $p>\tfrac12$ the single-head strategy One is
optimal, $n\mapsto w_{n,p}$ is strictly increasing, and $W(p)=\lim_n w_{n,p}$ has an explicit
series representation. In the regime $p<\tfrac12$, explicitly left open by van Doorn, a
first-order perturbation in $\delta=\tfrac12-p$ gives a closed-form description: the deficit
satisfies $\tfrac12-w_{n,1/2-\delta}\approx\delta c_n$, where $c_n$ obeys a linear recursion
for $n\ge7$ with limit $L\approx1.7035$, and to first order the optimal-value sequence has a
strict local minimum at $n=5$ and no local maximum.

Result

Proved

Status

Partial result

AI contribution

AI co-developed

Method

Argument

Field

Markov decision processes

Posed by

W. van Doorn (small-$p$ regime left open; game builds on a question of J. Breitner)

Year posed

2024

Years open

2y

Solved

2026-04-24

Model

Claude Opus 4.6 / 4.7 / 4.8

Vendor

Anthropic

Collaborators

Peter Pfaffelhuber

Verification

Lean-verified

Publication

Preprint

Significance

5 / 100*

Disclosed cost

—

Wikipedia

No dedicated article

Submitted by PluckyGecko226 on 01 Aug 2026