Journal of Integer Sequences, Vol. 12 (2009), Article 09.1.3

Introduction to the "Prisoners and Guards" Game

Timothy Howard, Eugen J. Ionascu, and David Woolbright
Department of Mathematics
Columbus State University
4225 University Avenue
Columbus, GA 31907


We study the half-dependent problem for the king graph Kn. We give proofs to establish the values h(Kn) for n ∈ {1,2,3,4,5,6} and an upper bound for h(Kn) in general. These proofs are independent of computer assisted results. Also, we introduce a two-player game whose winning strategy is tightly related with the values h(Kn). This strategy is analyzed here for n = 3 and some facts are given for the case n = 4. Although the rules of the game are very simple, the winning strategy is highly complex even for n = 4.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A103139.)

Received August 12 2008; revised versions received October 6 2008; October 18 2008. Published in Journal of Integer Sequences, December 14 2008.

Return to Journal of Integer Sequences home page