Flight over Bristol

Bristol Algorithms Days 2010
Feasibility Workshop

15 - 16 February 2010

  •    •    •  

Knights, Spies, Games and Social Networks

Mark Wildon

The aim of my talk will be to interest people in the Knights and Spies Problem and variations on its theme. The original problem is as follows. In a room there are 100 people. Each person is either a knight or a spy. Knights always tell the truth, but spies may lie or tell the truth as they see fit. It is given that everyone in the room knows the identity of everyone else, and that the knights strictly outnumber the spies. What is the minimum number of questions of the form

'Person i, what is the identity of person j?'

that will guarantee to find the true identities of all 100 people?

I will present an outline of my solution to this problem, concentrating on the techniques which seem likely to have a wider application. I will then discuss some interesting mathematical generalizations of the problem that are, as yet, unsolved. My talk will end with some more speculative variations on the problem, that I expect to be relevant to issues in the real world. Possible applications include key distribution and certificate signing in public-key cryptosystems, strategies for building on-line networks of reputable businesses, and the dynamics of evolution within and between species.


  The University of Bristol   EPSRC