Knights - knaves

[Guest]

On a fictional island there are 10 inhabitants, that know each other. Five of them are knights, who always tell the truth and the rest 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?

[Guest]

8 questions are needed.

If the islanders all told the truth, but were still split into knaves and knights, then there would be 252 possibilities ("10 choose 5" mathematically speaking). You could list all 252 possibilities and do a binary search on the list, asking an islander if the actual configuration is in the first half of the list or the second half, then throwing away half the list and repeating. You would need 7 or 8 questions to get the configuration (because [tex]2^7<252\leq 2^8[/tex]).

You can always get the truth out of an islander by prefixing the following to your question "Would the opposite type of person to you answer the following question with no : [Question]". For example:

If your question is, "Is 1+1=3?", asking a knight would mean the knight will tell you if a hypothetical knave will say no, a hypothetical knave would lie and say yes (1+1 equals 3), so the knight you're talking to will say no (the hypothetical knave wouldn't answer no), which is the correct answer.

If your question is, "Is 1+1=3?", asking a knave would mean the knave will lie to you about what a hypothetical knight will say, a hypothetical knight would be truthful and say no (1+1 does not equal 3), so the knave you're talking to will say no (they will lie and say the hypothetical knight didn't answer no), which is the correct answer.

So regardless if you ask a knight or knave the response will be no. If the question was changed to "Is 1+1=2?" then regardless if you ask a knight or knave the response will be yes (I leave that as an exercise for you to work through).

By prefixing the question with asking what the other type of person would do, you've introduced a negation to the answer, the answer sort of "passes through" a knight then a knave, or a knave then a knight, so exactly one lie occurs. By asking if the answer would be no, you've introduced another negation, and the two negations cancel to give the truth. This trick is pretty well known, due to a viral riddle, just search "two doors riddle", you'll get a similar puzzle about getting the truth out of an angel and devil guarding gates/doors.


Alternatively you could spend one of your questions asking an islander is "2+2=4" if they answer yes they are a knight, if they answer no they are a knave. You can then quiz this person about the other islanders (negating the answers if you choose a knave). There will be 126 possible configurations (9 choose 5 or equivalently 9 choose 4) of the remaining 9 islanders, you can list them and do a binary search, which will take at most another 7 questions.

Hope this helped,

R. Baber.

[Guest]

You would need 7 or 8 questions to get the configuration (because [tex]2^7<252≤2^8[/tex]).

Could you explain why?

[Guest]

Sorry that should read you need at most 8 questions. With each question you can split the list of configurations into two parts, in the worst case scenario you eliminate the part that is smaller, so it's in your best interest to make the parts as equal as possible (ideally exactly in half). So each question halves the possibilities, or put another way each extra question allows our list to be twice as big.

With 0 questions we can find the right configuration if our list is of size 1.
With 1 question we can deal with lists of size 2.
With 2 questions we can deal with lists of size 4.
With 3 questions we can deal with lists of size 8.
etc...
With 7 questions we can deal with lists of size 2^7 = 128 (which is too small).
With 8 questions we can deal with lists of size 2^8 = 256 (which is a bit bigger than we actually need).

Hope this helped,

R. Baber.

[Guest]

Correct, R. Baber!