wu :: forums « wu :: forums - Knights - knaves variation » Welcome, Guest. Please Login or Register. Nov 29th, 2021, 3:05am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, SMQ, Eigenray, ThudnBlunder, towr, Grimbal, william wu)    Knights - knaves variation « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Knights - knaves variation  (Read 823 times)
Altamira_64
Junior Member

Posts: 116
 Knights - knaves variation   « on: Dec 7th, 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 yes-no 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 7th, 2016, 12:30pm » Quote Modify

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

The maximum is (trivially) 5-9 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 7th, 2016, 12:32pm by dudiobugtron » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2844
 Re: Knights - knaves variation   « Reply #2 on: Dec 7th, 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 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.
 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 7th, 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 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.
 « Last Edit: Dec 7th, 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 7th, 2016, 11:21pm » Quote Modify

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

Correct.
 « Last Edit: Dec 7th, 2016, 11:22pm by Altamira_64 » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2844
 Re: Knights - knaves variation   « Reply #5 on: Dec 8th, 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 8th, 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 8th, 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 8th, 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 8th, 2016, 1:05pm » Quote Modify

on Dec 8th, 2016, 12:01pm, 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.
 « Last Edit: Dec 8th, 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 9th, 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.
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
Uberpuzzler

Posts: 1026
 Re: Knights - knaves variation   « Reply #10 on: Dec 9th, 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 9th, 2016, 2:33pm » Quote Modify

on Dec 9th, 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »