Draws in the undirected trapping game on percolation clusters
Fix an integer $d \ge 2$ and $p \in (0,1)$, and delete each vertex of the nearest-neighbour graph on $\mathbb{Z}^d$ independently with probability $p$. On the resulting graph, known to both players, they play Trap: a token starts at the origin, and the players alternately move it along an edge to an undeleted vertex that has not been visited before; a player with no legal move loses. If the origin is deleted, the first player is declared the winner. The board is a draw if neither player has a strategy that forces a win against every strategy of the opponent, and $D_d(p)$ is the probability of a draw. Without deletions Trap on $\mathbb{Z}^d$ is a draw, and there are almost surely no draws when $1 - p$ is below the critical probability for site percolation. On $\mathbb{Z}^2$ with odd and even vertices deleted with probabilities $p_{\mathrm{odd}} > 0$ and $p_{\mathrm{even}}$, Basu, Holroyd, Martin and Wästlund proved that almost surely no starting vertex gives a draw if $p_{\mathrm{even}}$ is small enough in terms of $p_{\mathrm{odd}}$, and the same on the body-centred lattice in every dimension $d \ge 3$.
Problem. For which dimensions $d \ge 2$ is there $p \in (0,1)$ with $D_d(p) > 0$? Is $D_2(p) = 0$ for every $p \in (0,1)$, while for every $d \ge 3$ there is $p \in (0,1)$ with $D_d(p) > 0$? The game is undirected and forbids revisiting vertices; directed percolation games have different rules.
Source: Basu, Holroyd, Martin and Wästlund (2016), final list of problems, item (i), who find it plausible that the answer is no for d = 2 and yes for d ≥ 3; stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, combinatorial games, site percolation
References
@article{basu2016,
author = {Basu, Riddhipratim and Holroyd, Alexander E. and Martin, James B. and W{\"a}stlund, Johan},
title = {Trapping games on random boards},
journal = {Ann. Appl. Probab.},
volume = {26},
number = {6},
year = {2016},
pages = {3727--3753},
doi = {10.1214/16-AAP1190},
eprint = {1505.07485},
archivePrefix = {arXiv},
}
@misc{aim-trap-draws-percolation,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Draws in the undirected trapping game on percolation clusters}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/574-trap-draws-percolation.md},
note = {Entry 574 at commit a153f46, 2026-10-13},
}
Resolution claims
Independently delete each vertex of the nearest-neighbor lattice $\Z^d$ with probability $p$. Two players, knowing the entire resulting board, move a token alternately to an undeleted neighbor that has never been visited; a player with no legal move loses. A draw means that neither player can force a win. We prove that the draw probability is zero in dimension two …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: AIM @ a153f46, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00775, "Draws in the undirected trapping game on percolation clusters", clopen.solutions.