wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Knights - knaves variation
        
(Message started by: Altamira_64 on Dec 7^th, 2016, 9:32am)

Title: Knights - knaves variation
Post by Altamira_64 on Dec 7^th, 2016, 9:32am

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?

Title: Re: Knights - knaves variation
Post by dudiobugtron on Dec 7^th, 2016, 12:30pm

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

The maximum is (trivially) [hide]5-9 questions[/hide], since you can just [hide]ask each person a question where its truth is common knowledge. Or, ask each person a variation of the 1 knight, 1 knave question.[/hide]

Title: Re: Knights - knaves variation
Post by rmsgrey on Dec 7^th, 2016, 2:21pm

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 10-inhabitant knight-knave 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 lower-bound of 8 questions is achievable or not.

Title: Re: Knights - knaves variation
Post by towr on Dec 7^th, 2016, 10:37pm

[hide]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 self-correcting 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.[/hide]

Title: Re: Knights - knaves variation
Post by Altamira_64 on Dec 7^th, 2016, 11:21pm

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

Correct.

Title: Re: Knights - knaves variation
Post by rmsgrey on Dec 8^th, 2016, 10:08am

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.

Title: Re: Knights - knaves variation
Post by Altamira_64 on Dec 8^th, 2016, 12:01pm

So the minimum number is 8, right?

Title: Re: Knights - knaves variation
Post by dudiobugtron on Dec 8^th, 2016, 12:02pm

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:

[hide]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")
?[/hide]

I'm sure there is a more elegant way to ask it though!

Title: Re: Knights - knaves variation
Post by towr on Dec 8^th, 2016, 1:05pm

on 12/08/16 at 12:01:43, Altamira_64 wrote:

So the minimum number is 8, right?

If the only information you're allowed to get from the yes-no 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 yes-no 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.

Title: Re: Knights - knaves variation
Post by rmsgrey on Dec 9^th, 2016, 8:34am

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
8) 1

The real question is how far those lists of possibilities can be compressed into something more elegant...

Title: Re: Knights - knaves variation
Post by rloginunix on Dec 9^th, 2016, 10:20am

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?

Title: Re: Knights - knaves variation
Post by dudiobugtron on Dec 9^th, 2016, 2:33pm

on 12/09/16 at 10:20:59, rloginunix wrote:

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.