  This paper presents a solution to the Knights and Spies Problem: In a room
there are n people, each labelled with a unique number between 1 and n. A
person may either be a knight or a spy. Knights always tell the truth, while
spies may either lie or tell the truth, as they see fit. Each person in the
room knows the identity of everyone else. Apart from this, all that is known is
that strictly more knights than spies are present. Asking only questions of the
form: `Person i, what is the identity of person j?', what is the least number
of questions that will guarantee to find the true identities of all n people?
The analysis of a related two-player game is critical to the proof. Some
probabilistic aspects are also explored. The paper ends by presenting three
open questions concerned with generalisations of the problem.
