How long can the robber survive 5k/2 cops on a cylinder?
On a k×m cylinder grid, k+1 cops catch the robber in Θ(m) rounds and 3k cops in O(log m). What happens with 5k/2 cops?
Cite
@misc{cairn-cops-robber-cylinder-rounds,
title = {How long can the robber survive 5k/2 cops on a cylinder?},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/cops-robber-cylinder-rounds}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/cops-robber-cylinder-rounds)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
In the Cops-and-Robber game on the k × m cylinder grid, how many rounds can the robber survive against 5k/2 cops?
What is known
k + 1 cops can catch the robber, but need Ω(m) rounds; 3k cops can catch the robber in O(log m) rounds. The question arose from lower-bound techniques in proof complexity that use such pursuit games.
What counts as progress
- Exact game values (minimal capture time) computed by retrograde analysis for small k and m, for numbers of cops between k + 1 and 3k, to see how the capture time scales with m.
- Cop strategies with proven capture times, or robber strategies with proven survival times.
How it is checked
Game-solving code and its output tables are reproducible (level B); strategies are reviewed or verified by the solver on small instances.
Source. Posed by Shuo Pang in the open problem session of the Oberwolfach workshop Proof Complexity and Beyond (2024), recorded in Oberwolfach Reports 15/2024, p. 876 (EMS Press, DOI 10.4171/OWR/2024/15), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.