wu :: forums
wu :: forums - Knights - knaves variation

Welcome, Guest. Please Login or Register.
Nov 21st, 2018, 10:51am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, ThudnBlunder, william wu, Grimbal, Icarus, SMQ, towr)
   Knights - knaves variation
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Knights - knaves variation  (Read 332 times)
Altamira_64
Junior Member
**





   


Posts: 116
Knights - knaves variation  
« on: Dec 7th, 2016, 9:32am »
Quote Quote Modify 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: 732
Re: Knights - knaves variation  
« Reply #1 on: Dec 7th, 2016, 12:30pm »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Knights - knaves variation  
« Reply #2 on: Dec 7th, 2016, 2:21pm »
Quote Quote Modify 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: male
Posts: 13649
Re: Knights - knaves variation  
« Reply #3 on: Dec 7th, 2016, 10:37pm »
Quote Quote Modify 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 Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Knights - knaves variation  
« Reply #5 on: Dec 8th, 2016, 10:08am »
Quote Quote Modify 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 Quote Modify Modify

So the minimum number is 8, right?
 
IP Logged
dudiobugtron
Uberpuzzler
*****





   


Posts: 732
Re: Knights - knaves variation  
« Reply #7 on: Dec 8th, 2016, 12:02pm »
Quote Quote Modify 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: male
Posts: 13649
Re: Knights - knaves variation  
« Reply #8 on: Dec 8th, 2016, 1:05pm »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Knights - knaves variation  
« Reply #9 on: Dec 9th, 2016, 8:34am »
Quote Quote Modify 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
Cool 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 9th, 2016, 10:20am »
Quote Quote Modify 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: 732
Re: Knights - knaves variation  
« Reply #11 on: Dec 9th, 2016, 2:33pm »
Quote Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board