The Prisoners and the Swap: Less than Half is Enough
Abstract
We improve the solution of the classical prisoners and drawers riddle, where all prisoners can find their number using the pointer-following strategy, provided that the prisoners can send a spy to inspect all drawers and swap one pair of numbers. In the traditional approach, each prisoner may need to open up to half of the drawers. We show that this strategy is sub-optimal. Remarkably, a single swap allows all $n$ prisoners to find their number by opening only $\frac{n \ln \ln n}{\ln n} (1 + o(1))$ drawers in the worst case. We show that no strategy can do better than that by a factor larger than two. Efficiently constructing such a strategy is harder, but we provide an explicit efficient strategy that requires opening only $O(\frac{n \log \log n}{\log n})$ drawers by each prisoner in the worst case.
Fields of Study & Subjects
Global Peace and Security Dynamics
European Criminal Justice and Data Protection
Historical and Contemporary Political Dynamics
Publication details
- Journal / source
- American Mathematical Monthly
- Publisher
- Informa UK Limited
- Volume
- 133
- Issue
- 5
- Pages
- 423–438
- Publication date
- 7 April 2026
- Language
- EN