The Prisoner Shouting Puzzle and Variations

Abstract

The following game, which we call the “Prisoner Shouting Puzzle,” pits prisoners against a prisoner warden. One hundred prisoners are each given a hat by the prison warden, and each hat has a label from 1 to 100. Repetition of labels is allowed. Each prisoner can see the other hats but not their own. The goal of the prisoners is for all 100 prisoners to simultaneously shout the same number, and for that number to be on at least one of the hats. The warden wants to prevent this.

This article is an in-depth discussion of Julian Rosen’s elegant solution to this puzzle. In this article, we prove Rosen’s strategy is indeed optimal, and in doing so, we find a nice connection to Sperner’s lemma. We also consider variations of this puzzle, where extensions of Rosen’s strategy are again optimal, but in surprising ways and to a remarkable level of generality.

• MSC: Primary 00A08
• Secondary 91A43
• 05C57

Acknowledgments

The authors wish to thank Julian Rosen for his insight that led to this article and the editors of the American Mathematical Monthly for their constructive comments, which greatly improved the quality of this article.

Additional information

Notes on contributors

Deborah E. Seacrest

Deborah E. Seacrest received a B.S. in Mathematics from Harvey Mudd College in 2006, an M.S. in Mathematics from the University of Nebraska–Lincoln in 2008, and a Ph.D. in Mathematics Education from the University of Nebraska–Lincoln in 2011. She teaches at the University of Montana Western and is particularly interested in both developmental education and recreational mathematics. She strives to combine what she has learned in both areas to improve her teaching.

Tyler Seacrest

Tyler Seacrest received a B.S. in Mathematics from Harvey Mudd College in 2006, and a Ph.D. in Mathematics from the University of Nebraska–Lincoln in 2011 studying graph theory. He now teaches at the University of Montana Western, where he tries to foster inquiry-based learning, undergraduate research, and connections to art, physics, biology, or any other topic that sparks student interest. [CrossRef]