Knights, spies, games and ballot sequences

Details Knights, spies, games and ballot sequences Knights, spies, games and ballot sequences

2009-03-16

arxiv.org/abs/0903.2869v1

Mathematics

Combinatorics

17 pages, 11 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Knights, spies, games and ballot sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Knights, spies, games and ballot sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Knights, spies, games and ballot sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-490829