Introduction to the Prisoners Versus Guards Game

Authors Timothy Howard, Eugen J. Ionascu, David E. Woolbright

Publication date 13 July 2009

Full work available at URL https://arxiv.org/abs/0801.0833, https://eudml.org/doc/55853, http://www.emis.de/journals/JIS/VOL12/Ionascu/ionascu.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

upper bounds domination in graphs winning strategies maximal configurations

Mathematics Subject Classification ID

2-person games (91A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: We introduce a two-player game in which one and his/her opponent attempt to pack as many ``prisoners as possible on the squares of an n-by-n checkerboard; each prisoner has to be ``protected by at least as many guards as the number of the other prisoners adjacent. Initially, the board is covered entirely with guards. The players take turns adjusting the board configuration using one of the following rules in each turn: I. Replace one guard with a prisoner of the player's color. II. Replace one prisoner of either color with a guard and replace two other guards with prisoners of the player's color. We analyze winning strategies for small n (n<5) and the maximum number of prisoners in general. We show that this maximum is less than (7n^2+4n)/11 and conjecture it is more likely 3n^2/5+O(n).

Recommendations

Cited in

(1)

Prisoners and guards on rectangular boards

Describes a project that uses

Uses Software

OEIS

This page was built for publication: Introduction to the Prisoners Versus Guards Game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637652)