In the classic knights and knaves problem, there are n people in a room each of whom is a knight or a knave. Knights always tell the truth while knaves always lie. Everyone in the room knows each other's identity. You are allowed to ask questions of the form "Person i, is person j a knight?" and you are told that there are more knights than knaves. What is the fewest number of questions you can ask to determine a knight? How about to determine everyone's identity? In this paper, we consider the knights and no-men problem, where a no-man is a person who always answers "no". Assuming there are at least k knights, we show that (n-1 2) - (「)(k-2)(n-1)~2/2(k-1)」 questions are necessary and sufficient in the worst case to identify a knight. We also show that n - 2 questions suffice to identify a no-man, and (n-1 2) - (「)(k-2)(n-1)~2/2(k-1)」+ n - 2 questions suffice to identify everyone in the room. We then consider a generalization of the knights and knaves problem that captures most of the variants of the knights and knaves problem in the literature. In the agent labeling problem, we wish to identify everyone's type; in the agent identification problem, we wish to identify an agent having a particular type. We present results with regards to the fewest number of questions needed in the worst case to solve both the agent labeling and agent identification problems. Our tools and results are graph theoretic in nature.
展开▼
