##
**
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

USA

**Abstract:**

We study the half-dependent problem for the king graph
*K*_{n}. We give proofs to establish the
values *h*(*K*_{n}) for *n*
∈ {1,2,3,4,5,6} and an
upper bound for *h*(*K*_{n}) 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*(*K*_{n}).
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**