Searching for knights and spies: A majority/minority game

Mark Wildon

Research output: Contribution to journalArticlepeer-review

77 Downloads (Pure)


There are n people, each of whom is either a knight or a spy. It is known that at least k knights are present, where n/2 < k < n. Knights always tell the truth. We consider both spies who always lie and spies who answer as they see fit. This paper determines the minimum number of questions required to find a spy or prove that everyone in the room is a knight. We also determine the minimum number of questions needed to find at least one person’s identity, or a nominated person’s identity, or to find a spy (under the assumption that a spy is present). For spies who always lie, we prove that these searching problems, and the problem of finding a knight, can be solved by a simultaneous optimal strategy. We also give some computational results on the problem of finding all identities when spies always lie, which show that a plausible suggestion made by Aigner is false. We end by stating some open problems. The questioning strategies in the paper have applications to fault finding in distributed computing networks.
Original languageEnglish
Pages (from-to)2754–2766
Number of pages13
JournalDiscrete Mathematics
Issue number11
Early online date11 Jun 2016
Publication statusPublished - 6 Nov 2016

Cite this