×

Prisoners and guards on rectangular boards. (English) Zbl 1297.05161

Summary: R. Aharoni et al. [J. Comb. Theory, Ser. B 50, No. 1, 1–10 (1990; Zbl 0717.05065)] 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. T. Howard et al. [J. Integer Seq. 12, No. 1, Article ID 09.1.3, 19 p. (2009; Zbl 1167.91005)] 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 \leq 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\).

MSC:

05C57 Games on graphs (graph-theoretic aspects)
91A05 2-person games
91A43 Games involving graphs
05A15 Exact enumeration problems, generating functions
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: EMIS