Journal of Integer Sequences, Vol. 17 (2014), Article 14.8.1

Prisoners and Guards on Rectangular Boards


Grady Bullington, Linda Eroh, and Steven J. Winters
Mathematics Department
University of Wisconsin, Oshkosh
800 Algoma Blvd.
Oshkosh, WI 54901
USA

Abstract:

Woolbright introduced the "Prisoners and Guards" game as a two-player game on an n × n checkerboard. At the beginning of the game, every square of the board has a guard. At each stage in the game, for each prisoner, there must be at least as many guards as prisoners on adjacent squares. The players take turns either replacing a guard with a prisoner in their color or replacing one prisoner (of either color) with a guard, then replacing two guards with prisoners in their color, subject to the rule above. When neither player can adjust the board any further, the player with more prisoners in their color wins. Howard, Ionascu, and Woolbright gave formulas for the maximum number of prisoners on n × n boards. In this paper, we give formulas for the number of prisoners in the maximum configurations of n × m boards, where 2 ≤ n < m, for n = 2, 3, and 5, upper and lower bounds that differ by less than 2 when n = 4, and a lower bound for n = 6.


Full version:  pdf,    dvi,    ps,    latex    


Received September 17 2013; revised version received January 24 2014; June 3 2014; July 16 2014. Published in Journal of Integer Sequences, July 18 2014. Revised, July 17 2015; July 30 2015.


Return to Journal of Integer Sequences home page