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

—

Disclosed cost

—

Wikipedia

No dedicated article

Submitted by PluckyGecko226