Prisoners and guards on rectangular boards

Bullington, Grady ; Eroh, Linda ; Winters, Steven J.

Journal of integer sequences, Tome 17 (2014) no. 8.

Résumé

Summary: Aharoni, Milner and Prikry introduced the "Prisoners and Guards" game as a two-player game on an $n \times 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 \times n$ boards. In this paper, we give formulas for the number of prisoners in the maximum configurations of $n \times m$ boards, where $2 \le 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$.

Détail

Classification : 05A15
Keywords: domination, half-domination, alliance, global offensive alliance