Author 
Topic: Knights  knaves variation (Read 804 times) 

Altamira_64
Junior Member
Posts: 116


Knights  knaves variation
« on: Dec 7^{th}, 2016, 9:32am » 
Quote Modify

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 yesno questions he must ask the inhabitants in order to find the 5 knaves?


IP Logged 



dudiobugtron
Uberpuzzler
Posts: 735


Re: Knights  knaves variation
« Reply #1 on: Dec 7^{th}, 2016, 12:30pm » 
Quote Modify

Each question must be to only one person, I assume (otherwise it's pretty easy). The maximum is (trivially) 59 questions, since you can just ask each person a question where its truth is common knowledge. Or, ask each person a variation of the 1 knight, 1 knave question.

« Last Edit: Dec 7^{th}, 2016, 12:32pm by dudiobugtron » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: Knights  knaves variation
« Reply #2 on: Dec 7^{th}, 2016, 2:21pm » 
Quote Modify

There are 252 possible ways of picking 5 knaves out of 10 inhabitants, so a general solution must take at least 8 questions to enable you to distinguish between more than 128 possibilities. With more general 10inhabitant knightknave islands, which have 1024 possible arrangements of knights and knaves, it's trivially both necessary and sufficient to ask 10 questions to identify them all. For this special island, you can improve the upper bound to 9 questions by observing that once you know 9 of the inhabitants' natures, you get the 10th automatically. It's not obvious whether the lowerbound of 8 questions is achievable or not.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13729


Re: Knights  knaves variation
« Reply #3 on: Dec 7^{th}, 2016, 10:37pm » 
Quote Modify

Once you know what the first person is, you can use the next 7 questions to determine which of 126 permutations you have for the rest. And that's without resorting to tricky selfcorrecting questions like "Would an inhabitant that's the opposite to your type say that .... ?" You can just ask the first person whether he's a pizza, and interpret his following answers accordingly.

« Last Edit: Dec 7^{th}, 2016, 10:41pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Altamira_64
Junior Member
Posts: 116


Re: Knights  knaves variation
« Reply #4 on: Dec 7^{th}, 2016, 11:21pm » 
Quote Modify

Each question must be to only one person, I assume (otherwise it's pretty easy). Correct.

« Last Edit: Dec 7^{th}, 2016, 11:22pm by Altamira_64 » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: Knights  knaves variation
« Reply #5 on: Dec 8^{th}, 2016, 10:08am » 
Quote Modify

Yeah, on further reflection, it's obvious that you can meet the lower bound (as towr says)  the tricky part is doing so in an elegant fashion.


IP Logged 



Altamira_64
Junior Member
Posts: 116


Re: Knights  knaves variation
« Reply #6 on: Dec 8^{th}, 2016, 12:01pm » 
Quote Modify

So the minimum number is 8, right?


IP Logged 



dudiobugtron
Uberpuzzler
Posts: 735


Re: Knights  knaves variation
« Reply #7 on: Dec 8^{th}, 2016, 12:02pm » 
Quote Modify

I think this question should always generate a correct answer as to whether the arrangement of knights and knaves fits a particular criterion, regardless of whether the person you ask is a knight or a knave: Is the following true: ("You are a knight" and "The arrangement of knights and knaves fits criterion X") or ("You are a knave" and "The arrangement of knights and knaves does not fit criterion X") ? I'm sure there is a more elegant way to ask it though!

« Last Edit: Dec 8^{th}, 2016, 12:03pm by dudiobugtron » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13729


Re: Knights  knaves variation
« Reply #8 on: Dec 8^{th}, 2016, 1:05pm » 
Quote Modify

on Dec 8^{th}, 2016, 12:01pm, Altamira_64 wrote:So the minimum number is 8, right? 
 If the only information you're allowed to get from the yesno question is yes or no, then yeah. You need almost 8 bits of information. And 8 is also sufficient. (You can slice the number of possible configurations in half with each yes/no question.) On the other hand, if you can give instructions via a yesno question and they're willing to follow them, then you might be able to do better: "Will you please separate the inhabitants of this island into two groups, one consisting of only knaves and the other consisting of only knights?" If the answer is yes, and the corresponding instruction is followed, well, you still won't know if it's true, but you're getting somewhere.

« Last Edit: Dec 8^{th}, 2016, 1:08pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: Knights  knaves variation
« Reply #9 on: Dec 9^{th}, 2016, 8:34am » 
Quote Modify

So, best approach we've come up with so far is: 1) Ask someone a question that identifies them 2) Ask that person "are the inhabitants of this island one of these 64 possibilities?" and then list 64 different possibilities. 3) Ask that person about a list of 32 possibilities 4) 16 5) 8 6) 4 7) 2 1 The real question is how far those lists of possibilities can be compressed into something more elegant...


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Knights  knaves variation
« Reply #10 on: Dec 9^{th}, 2016, 10:20am » 
Quote Modify

Can any advantage be squeezed out of forcing a predetermined geometric formation onto the remaining 9 suspects  by placing them, say, along a circumference of a circle and crafting the lists accordingly?


IP Logged 



dudiobugtron
Uberpuzzler
Posts: 735


Re: Knights  knaves variation
« Reply #11 on: Dec 9^{th}, 2016, 2:33pm » 
Quote Modify

on Dec 9^{th}, 2016, 10:20am, rloginunix wrote:Can any advantage be squeezed out of forcing a predetermined geometric formation onto the remaining 9 suspects  by placing them, say, along a circumference of a circle and crafting the lists accordingly? 
 For elegance  yes. EG: "Are there more knights to your right than to your left?", etc... But you can't reduce the required number of steps this way.


IP Logged 



