by **Guest** » Sat Dec 10, 2016 5:41 am

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.