# Thread: Knights - knaves puzzle

1. ## Knights - knaves puzzle

On a fictional island there are 10 inhabitants, who all know each other, of which 5 are knights, who always tell the truth and the rest of them are knaves, who always lie.
A visitor to the island wants to determine the 5 knaves. What is the minimum number of yes-no questions he must ask the inhabitants in order to find the 5 knaves?

2. ## Re: Knights - knaves puzzle

You ask the clever question of the each person you meet, which allows you to determine what he is. Do this at most nine times and you have identified all five of one group. Once you have your clever question, you use the Pigeonhole Principle to prove that you need no more than nine questions.

Edit: The clever question is not remotely clever.

3. ## Re: Knights - knaves puzzle

and what is this "clever question"? What do you mean "is not remotely clever"?

4. ## Re: Knights - knaves puzzle

Originally Posted by Alderamin
and what is this "clever question"? What do you mean "is not remotely clever"?
one would be

If I was a knight would you call me a knight or a knave? Or some such.

Get them to respond about a given fact.

5. ## Re: Knights - knaves puzzle

Originally Posted by romsek
Get them to respond about a given fact.
"Are you wearing a hat?" or "Can you fly?" would do.

We might be able to do better by treating groups. I'm thinking of the sort of puzzle where you have a balance and number of balls and one (or in this case) half is either heavier or lighter than the rest.

The question "does this group have more knights than that group" is putting the groups on the balance. The problem is that a balance answers in ternary, not binary.

6. ## Re: Knights - knaves puzzle

Originally Posted by Archie
"Can you fly?" would do.
and wouldn't you be surprised when they answered yes and flew off!

7. ## Re: Knights - knaves puzzle

Ask A "Would you say that you are a knight if you were asked whether you are a knight or a knave?"

If A is a knave, he would falsely answer "knight" if asked about his status so he will falsely answer "no" to the hypothetical question. If A is a knight, he will truthfully answer "knight" if asked about his status so he will truthfully answer "yes" to the hypothetical question.

If A answers "no," you have identified one knave. So you could round up B, C, D, and E and ask A whether they are all knaves. If the answer is "no," then A, B, C, D, and E are the knaves. If A answers "yes," you have identified one knight. So you could round up B, C, D, and E and ask A whether they are all knights. If the answer is "yes," then F, G, H, I, and J are the knaves. So you MAY be able to identify all the knaves with just two questions. So the answer to your question as I understand it is 2. In any case, you will be able to determine the truth value of any further answer from A.

But perhaps your question is what is the minimum number of questions that are guaranteed to classify correctly every one as a knight or a knave.

8. ## Re: Knights - knaves puzzle

But perhaps your question is what is the minimum number of questions that are guaranteed to classify correctly every one as a knight or a knave.[/QUOTE]

Yes. We want to precisely identify all 10 (which means that if we identify, say, the 5 knights, we are done).

9. ## Re: Knights - knaves puzzle

I think I'm close to one question. There might be a hole. I'm not sure.
JeffM's answer was good for putting me on the right track.

Ask an inhabitant X: "If you were the opposite of who you were, (supposing knights and knaves are opposites) who out of the remaining 9 would you call a knave?"

If X is a Knight: Has to tell the truth that, "supposing he were a knave, he would point to knights." Hence he'd point to 4 Knights.
If X is a Knave: Has to lie about that "supposing he were a knight, he would point to knaves." Hence he'd point to the 5 Knights.

Either way you know which are knights or knaves. If I'm wrong, I'm still convinced the crux of a one question answer would rely on a 4-5 person inequality.

10. ## Re: Knights - knaves puzzle

Is one plus one = two ?

Worse case:
yes's and no's tied after 8

So 9.