Author |
Topic: Knights - knaves variation (Read 1013 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: 2874
|
|
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: 13730
|
|
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: 2874
|
|
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: 13730
|
|
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: 2874
|
|
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.
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: 1029
|
|
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print