Island of Knights, Knaves and SpiesAbout the island of Knights and KnavesAbout Knights and Knaves and their consistencyThe way to Acarien, with Knights and KnavesIf The Knights and Knaves got togetherKnights , Knaves and Spies - Part 1Knights , Knaves and Spies - Part 2Meta Knights and Knaves Puzzle with HatsKnights, Knaves and Normals - the tough oneKnights Knaves and SpiesSolve the following knights and knaves problem
If Earth is tilted, why is Polaris always above the same spot?
Is thermodynamics only applicable to systems in equilibrium?
In the time of the mishna, were there Jewish cities without courts?
How to replace the "space symbol" (squat-u) in listings?
How do I tell my manager that he's wrong?
Phrase for the opposite of "foolproof"
Subtleties of choosing the sequence of tenses in Russian
Are Boeing 737-800’s grounded?
What's the polite way to say "I need to urinate"?
How can Republicans who favour free markets, consistently express anger when they don't like the outcome of that choice?
Unexpected email from Yorkshire Bank
Why does processed meat contain preservatives, while canned fish needs not?
When and why did journal article titles become descriptive, rather than creatively allusive?
Pulling the rope with one hand is as heavy as with two hands?
Any examples of headwear for races with animal ears?
Why does nature favour the Laplacian?
Do I have to worry about players making “bad” choices on level up?
How to create an ad-hoc wireless network in Ubuntu
Do I have an "anti-research" personality?
Past Perfect Tense
Minimum value of 4 digit number divided by sum of its digits
Transfer over $10k
Build a trail cart
How to set the font color of quantity objects (Version 11.3 vs version 12)?
Island of Knights, Knaves and Spies
About the island of Knights and KnavesAbout Knights and Knaves and their consistencyThe way to Acarien, with Knights and KnavesIf The Knights and Knaves got togetherKnights , Knaves and Spies - Part 1Knights , Knaves and Spies - Part 2Meta Knights and Knaves Puzzle with HatsKnights, Knaves and Normals - the tough oneKnights Knaves and SpiesSolve the following knights and knaves problem
$begingroup$
There is an island with $N$ inhabitants (for example $A_1, A_2, dots, A_N$), each of them is either a knight, a knave, or a spy. As usual:
knights will always tell the truth upon answering a question,
knaves will always lie,- and spies can do both (however they always alternate the truth value of their answers, i.e. if they lied they definitely will tell the truth upon the next answer, and vice versa).
You must determine the correct identities of all $A_i$'s by asking questions, which have to be of one of the following forms:
- Is $A_j$ a knight/knave/spy? (It includes the $i=j$ case, so you particularly can ask "Are you a knight/knave/spy?") The answer will be either "yes" or "no".
- How many knights/knaves/spies are among you? The answer will be an integer between $0$ and $N$, inclusively (so, for example for $N=20$, even a knave wouldn't answer $25$, $-3$, or $8.5$).
It's very easy to construct a solution with $2N$ questions, namely asking each islander twice: "Are you a spy?", because
- a knight will say "no" at both times (since knights never lie, and a knight is indeed not a spy),
- a knave will say "yes" both times (vice versa, a knave always lies, and still isn't a spy),
- and a spy will give different answers each time (because spies never lie or tell the truth twice in a row).
So, after 2 questions we can reveal the identity of one given islander.
The question to this puzzle is: Can the number of questions be less than $2N$, and if it can, what's the minimum number of questions needed? (In the solution above, the second type of questions was not even used.)
Update (some clarifications):
- As usual, the question is about the worst case (i.e. a strategy that guarantees the identifying after specified number of questions (with 100% probability)).
- All islanders know the identities of each other.
- Groups cannot be subdivided (the "second-type" question always refer to the whole set).
combinatorics optimization liars
asked Apr 25 at 10:49
trolley813trolley813
1,476410
$endgroup$
|
show 1 more comment
$begingroup$
There is an island with $N$ inhabitants (for example $A_1, A_2, dots, A_N$), each of them is either a knight, a knave, or a spy. As usual:
knights will always tell the truth upon answering a question,
knaves will always lie,- and spies can do both (however they always alternate the truth value of their answers, i.e. if they lied they definitely will tell the truth upon the next answer, and vice versa).
You must determine the correct identities of all $A_i$'s by asking questions, which have to be of one of the following forms:
- Is $A_j$ a knight/knave/spy? (It includes the $i=j$ case, so you particularly can ask "Are you a knight/knave/spy?") The answer will be either "yes" or "no".
- How many knights/knaves/spies are among you? The answer will be an integer between $0$ and $N$, inclusively (so, for example for $N=20$, even a knave wouldn't answer $25$, $-3$, or $8.5$).
It's very easy to construct a solution with $2N$ questions, namely asking each islander twice: "Are you a spy?", because
- a knight will say "no" at both times (since knights never lie, and a knight is indeed not a spy),
- a knave will say "yes" both times (vice versa, a knave always lies, and still isn't a spy),
- and a spy will give different answers each time (because spies never lie or tell the truth twice in a row).
So, after 2 questions we can reveal the identity of one given islander.
The question to this puzzle is: Can the number of questions be less than $2N$, and if it can, what's the minimum number of questions needed? (In the solution above, the second type of questions was not even used.)
Update (some clarifications):
- As usual, the question is about the worst case (i.e. a strategy that guarantees the identifying after specified number of questions (with 100% probability)).
- All islanders know the identities of each other.
- Groups cannot be subdivided (the "second-type" question always refer to the whole set).
combinatorics optimization liars
asked Apr 25 at 10:49
trolley813trolley813
1,476410
$endgroup$
1
$begingroup$
I take it we should assume that all the islanders know what everyone is?
$endgroup$
– Gareth McCaughan♦
Apr 25 at 11:13
$begingroup$
I assume you are looking for a strategy that guarantees that you will know the identity of every islander with fewer than 2N questions even in the worst case. Correct?
$endgroup$
– Hugh Meyers
Apr 25 at 13:22
$begingroup$
... and if so, then I suppose the worst case has to be that everyone is a knave thus making the second question valueless.
$endgroup$
– Hugh Meyers
Apr 25 at 13:27
6
$begingroup$
Can I subdivide groups? For example, If I split off a group of M < N and ask the second question, will they respond (0..M) or (0..N)?
$endgroup$
– Chris Cudmore
Apr 25 at 14:28
$begingroup$
@GarethMcCaughan Thanks for noticing! I've done some clarifications.
$endgroup$
– trolley813
2 days ago
|
show 1 more comment
$begingroup$
There is an island with $N$ inhabitants (for example $A_1, A_2, dots, A_N$), each of them is either a knight, a knave, or a spy. As usual:
knights will always tell the truth upon answering a question,
knaves will always lie,- and spies can do both (however they always alternate the truth value of their answers, i.e. if they lied they definitely will tell the truth upon the next answer, and vice versa).
You must determine the correct identities of all $A_i$'s by asking questions, which have to be of one of the following forms:
- Is $A_j$ a knight/knave/spy? (It includes the $i=j$ case, so you particularly can ask "Are you a knight/knave/spy?") The answer will be either "yes" or "no".
- How many knights/knaves/spies are among you? The answer will be an integer between $0$ and $N$, inclusively (so, for example for $N=20$, even a knave wouldn't answer $25$, $-3$, or $8.5$).
It's very easy to construct a solution with $2N$ questions, namely asking each islander twice: "Are you a spy?", because
- a knight will say "no" at both times (since knights never lie, and a knight is indeed not a spy),
- a knave will say "yes" both times (vice versa, a knave always lies, and still isn't a spy),
- and a spy will give different answers each time (because spies never lie or tell the truth twice in a row).
So, after 2 questions we can reveal the identity of one given islander.
The question to this puzzle is: Can the number of questions be less than $2N$, and if it can, what's the minimum number of questions needed? (In the solution above, the second type of questions was not even used.)
Update (some clarifications):
- As usual, the question is about the worst case (i.e. a strategy that guarantees the identifying after specified number of questions (with 100% probability)).
- All islanders know the identities of each other.
- Groups cannot be subdivided (the "second-type" question always refer to the whole set).
combinatorics optimization liars
asked Apr 25 at 10:49
trolley813trolley813
1,476410
$endgroup$
There is an island with $N$ inhabitants (for example $A_1, A_2, dots, A_N$), each of them is either a knight, a knave, or a spy. As usual:
knights will always tell the truth upon answering a question,
knaves will always lie,- and spies can do both (however they always alternate the truth value of their answers, i.e. if they lied they definitely will tell the truth upon the next answer, and vice versa).
You must determine the correct identities of all $A_i$'s by asking questions, which have to be of one of the following forms:
- Is $A_j$ a knight/knave/spy? (It includes the $i=j$ case, so you particularly can ask "Are you a knight/knave/spy?") The answer will be either "yes" or "no".
- How many knights/knaves/spies are among you? The answer will be an integer between $0$ and $N$, inclusively (so, for example for $N=20$, even a knave wouldn't answer $25$, $-3$, or $8.5$).
It's very easy to construct a solution with $2N$ questions, namely asking each islander twice: "Are you a spy?", because
- a knight will say "no" at both times (since knights never lie, and a knight is indeed not a spy),
- a knave will say "yes" both times (vice versa, a knave always lies, and still isn't a spy),
- and a spy will give different answers each time (because spies never lie or tell the truth twice in a row).
So, after 2 questions we can reveal the identity of one given islander.
The question to this puzzle is: Can the number of questions be less than $2N$, and if it can, what's the minimum number of questions needed? (In the solution above, the second type of questions was not even used.)
Update (some clarifications):
- As usual, the question is about the worst case (i.e. a strategy that guarantees the identifying after specified number of questions (with 100% probability)).
- All islanders know the identities of each other.
- Groups cannot be subdivided (the "second-type" question always refer to the whole set).
combinatorics optimization liars
combinatorics optimization liars
asked Apr 25 at 10:49
trolley813trolley813
1,476410
asked Apr 25 at 10:49
trolley813trolley813
1,476410
edited 2 days ago
trolley813
asked Apr 25 at 10:49
trolley813trolley813
1,476410
asked Apr 25 at 10:49
trolley813trolley813
1,476410
asked Apr 25 at 10:49
trolley813trolley813
1,476410
1,476410
1
$begingroup$
I take it we should assume that all the islanders know what everyone is?
$endgroup$
– Gareth McCaughan♦
Apr 25 at 11:13
$begingroup$
I assume you are looking for a strategy that guarantees that you will know the identity of every islander with fewer than 2N questions even in the worst case. Correct?
$endgroup$
– Hugh Meyers
Apr 25 at 13:22
$begingroup$
... and if so, then I suppose the worst case has to be that everyone is a knave thus making the second question valueless.
$endgroup$
– Hugh Meyers
Apr 25 at 13:27
6
$begingroup$
Can I subdivide groups? For example, If I split off a group of M < N and ask the second question, will they respond (0..M) or (0..N)?
$endgroup$
– Chris Cudmore
Apr 25 at 14:28
$begingroup$
@GarethMcCaughan Thanks for noticing! I've done some clarifications.
$endgroup$
– trolley813
2 days ago
|
show 1 more comment
1
$begingroup$
I take it we should assume that all the islanders know what everyone is?
$endgroup$
– Gareth McCaughan♦
Apr 25 at 11:13
$begingroup$
I assume you are looking for a strategy that guarantees that you will know the identity of every islander with fewer than 2N questions even in the worst case. Correct?
$endgroup$
– Hugh Meyers
Apr 25 at 13:22
$begingroup$
... and if so, then I suppose the worst case has to be that everyone is a knave thus making the second question valueless.
$endgroup$
– Hugh Meyers
Apr 25 at 13:27
6
$begingroup$
Can I subdivide groups? For example, If I split off a group of M < N and ask the second question, will they respond (0..M) or (0..N)?
$endgroup$
– Chris Cudmore
Apr 25 at 14:28
$begingroup$
@GarethMcCaughan Thanks for noticing! I've done some clarifications.
$endgroup$
– trolley813
2 days ago
1
1
$begingroup$
I take it we should assume that all the islanders know what everyone is?
$endgroup$
– Gareth McCaughan♦
Apr 25 at 11:13
$begingroup$
I take it we should assume that all the islanders know what everyone is?
$endgroup$
– Gareth McCaughan♦
Apr 25 at 11:13
$begingroup$
I assume you are looking for a strategy that guarantees that you will know the identity of every islander with fewer than 2N questions even in the worst case. Correct?
$endgroup$
– Hugh Meyers
Apr 25 at 13:22
$begingroup$
I assume you are looking for a strategy that guarantees that you will know the identity of every islander with fewer than 2N questions even in the worst case. Correct?
$endgroup$
– Hugh Meyers
Apr 25 at 13:22
$begingroup$
... and if so, then I suppose the worst case has to be that everyone is a knave thus making the second question valueless.
$endgroup$
– Hugh Meyers
Apr 25 at 13:27
$begingroup$
... and if so, then I suppose the worst case has to be that everyone is a knave thus making the second question valueless.
$endgroup$
– Hugh Meyers
Apr 25 at 13:27
6
6
$begingroup$
Can I subdivide groups? For example, If I split off a group of M < N and ask the second question, will they respond (0..M) or (0..N)?
$endgroup$
– Chris Cudmore
Apr 25 at 14:28
$begingroup$
Can I subdivide groups? For example, If I split off a group of M < N and ask the second question, will they respond (0..M) or (0..N)?
$endgroup$
– Chris Cudmore
Apr 25 at 14:28
$begingroup$
@GarethMcCaughan Thanks for noticing! I've done some clarifications.
$endgroup$
– trolley813
2 days ago
$begingroup$
@GarethMcCaughan Thanks for noticing! I've done some clarifications.
$endgroup$
– trolley813
2 days ago
|
show 1 more comment
5 Answers
5
active
oldest
votes
$begingroup$
It takes
at most about $5N/3$ questions.
Suppose
we know a knight or spy and want to find the identities of $k$ islanders. We can find the division of $k$ into knights, knaves, or spies by asking the knight/spy at most five questions of the second type. Suppose the most represented type is X. Then we ask the knight/spy whether each of the $k$ is X. This determines exactly which of them is X, so we can determine the remainder by asking the knight/spy whether each of them is one of the remaining types. In the worst case, each of the classes is equally represented among the $k$, so that this takes about $5k/3$ questions.
Now
our strategy is to find a knight/spy. First we use the known two question strategy to determine the identity of an islander. If they are a knave, we keep asking them whether other islanders are knaves. Each knave discovered in this way requires only one question, so in the worst case we quickly discover a knight/spy, and we use about $5N/3$ questions in total.
answered Apr 25 at 14:19
noednenoedne
9,93212769
$endgroup$
$begingroup$
It seems like there is a bit of a flaw: If we identify a spy, then we can't simply find which of the k are type X in k questions by asking the spy "is A_i of type X?" because we will get lies every other time. We are not allowed to ask "or" questions.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@BoltonBailey We know the truth/lie pattern, so we can just negate the lies.
$endgroup$
– noedne
2 days ago
$begingroup$
You can't just negate the lies. You are only allowed to ask questions of the given forms, not their negations.
$endgroup$
– Bolton Bailey
2 days ago
2
$begingroup$
@BoltonBailey Negate the answer, not the question.
$endgroup$
– noedne
2 days ago
$begingroup$
Yep. That works.
$endgroup$
– Bolton Bailey
2 days ago
|
show 5 more comments
$begingroup$
Assuming inhabitants know the identity of other inhabitants and a bit of math, for N inhabitants, I believe you could find the identity of every inhabitant with a number of questions approximately equal to
$3 + frac(N - 1) * log(3)log(2)$
Here's how:
Take aside one inhabitant and figure out, using the 2 questions in the
question to determine whether the inhabitant is a knight, a knave or a
spy.
.
If faced with a spy, ask, as a third question, whether or not he or
she is a spy. This will tell you which "phase" the spy is in, allowing
you to determine the truth value of future answers. If the spy says he
is not a spy, then that is a lie, and his next answer will be the
truth. If the spy admits to being a spy, his next answer will be a
lie, and so on.
.
You now have one person you can use to find out the true answer to any
question. (Taking the negation if you have a knave) Let's hope this
person is patient and knows a bit of math. You will be asking him a
series of questions.
.
You will line up all of the other N-1 inhabitants and ask the
inhabitant whose identity has been determined to compute a trinary
number where each trinary digit corresponds to one of the other N-1
inhabitants: 0 if the inhabitant is a knight, 1 if a knave and 2 if a
spy. For a trinary number with N-1 digits, there are $3^N-1$
possibilities.
A binary search will then allow you to eliminate half of these
possibilities with a single question, repeating until there is only
one option.
answered Apr 25 at 19:24
Vincent B. LortieVincent B. Lortie
312
New contributor
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Could you elaborate on your last paragraph? I'm not convinced that a binary search is possible under the restrictions of the questions - how would it be done?
$endgroup$
– hexomino
Apr 25 at 19:55
$begingroup$
That being said, this answer is pretty useful as I think it provides a lower bound. It's pretty close to noedne's answer which makes me think that is the best that could be achieved.
$endgroup$
– hexomino
Apr 25 at 20:00
$begingroup$
@hexomino We know both the biggest and smallest possible N-digit trinary numbers: N^3-1 and 0. Take the halfway point, ask if the number I described in my answer is greater or lesser than, then repeat on the reduced range.
$endgroup$
– Vincent B. Lortie
Apr 26 at 2:17
1
$begingroup$
It's not clear to me that this question about the trinary number can be asked in the form of one of the two questions types allowed.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@VincentB.Lortie Yes, I agree with what Bolton Bailey says, you are only permitted to ask either "Is A_i a knight/knave/spy?" or "How many among you are knights/knaves/spies?" You are not permitted to ask questions about a trinary number.
$endgroup$
– hexomino
2 days ago
add a comment |
$begingroup$
Some upper bounds on the number of questions needed have been provided. Here is a lower bound:
Based on information theory. Suppose that $N = 3k$ and that before our interrogation, we are told that the true number of knights, knaves and spies are each $k$. Thus, asking questions of the second kind is equivalent to querying whether a individual is telling the truth this round. This imparts 1 bit of information. Similarly, questions of the first kind impart 1 bit of information, because they are Yes/No questions. Since the total number of possibilities is $binom3kk,k,k ge (3k/k)^k(2k/k)^k = 6^k$, we will still need $log_2 6^k = k log_2 6 = N frac13 log_2 6 approx N * 0.86$
answered 2 days ago
Bolton BaileyBolton Bailey
1314
New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Wrong answer
[EDITED to add:] Oops, the following is all wrong; thanks to @hexomino for pointing out in comments that I misinterpreted the question. I'm leaving this here rather than deleting it because (1) it's possible that some idea in it is salvageable and (2) I don't believe in making myself look better by deleting my mistakes :-). (I might delete it later to reduce clutter.)
The minimal number of questions
is less than $2N$, at least when $N$ is not too small. In fact, it's never more than $frac43N$ plus a few.
Here's why.
First, use two "are you a spy?" questions to establish what #1 is, and also (if they're a spy) which way around their truth-telling and lying answers are. We now have three cases. If #1 is a knight then we can just ask them about everyone else, and we're done in $N+1$ questions. If #1 is a spy then we ask them about everyone else -- once, asking "what is X?", when they are telling the truth, and twice, asking binary questions, when they are lying. Every 4 questions we find out about 3 people, so we take approximately $frac43N$ questions.
The hardest case is when #1 is a knave. Here's one way to proceed. Ask them "is X a knave?" about each other person in turn. If they say "no" then we have correctly identified that X is a knave, and if that's all that ever happens then again we're done in $N+1$ questions. If at some point they say "yes" then we have found a non-knave. We can then ask that person two questions to figure out exactly what they are and (if they're a spy) what their "phase" is, and then proceed as above, asking them about everyone else in turn.
In the worst case: we take two questions to establish that #1 is a knave; we take one more question to establish that #2 is knot a knave; we take two questions to establish that #2 is a spy and phind his phase; we then have $N-2$ people to figure out, divide them into $leftlceilfracN-23rightrceil$ groups of at most 3, and use 4 questions for each group, for a total of $leftlceilfracN-23rightrceil+5$ questions. I make no claim that this is optimal, though.
answered Apr 25 at 13:57
Gareth McCaughan♦Gareth McCaughan
68.7k3174269
$endgroup$
2
$begingroup$
I think if #1 is a knight we still need 2N-2 questions because you can only ask questions like "Is A_j a knight?" not "What is A_j?" meaning that in the worst case you would still need two questions to determine each one, right?
$endgroup$
– hexomino
Apr 25 at 14:02
$begingroup$
oh, damn, I misread the question. You're right; we don't get to ask "what is X?" questions at all.
$endgroup$
– Gareth McCaughan♦
Apr 25 at 14:03
add a comment |
$begingroup$
The minimum number of questions needed is
2, but only if you're lucky
How?
You ask the first person:
"Are you a spy?"
"No."
"How many knights are there?"
"N"
After the first question, they're either a knight or a lying spy. Either way, the next answer will be truthful. And since that truthful answer indicated that everyone is a knight, clearly they're also a knight.
And you're done! They're all knights!
answered Apr 25 at 21:02
Arcanist LupusArcanist Lupus
42218
$endgroup$
1
$begingroup$
This can actually be reduced to two questions, if you're very lucky. Can you see how? This interpretation, in itself, is a good mini-puzzle.
$endgroup$
– hexomino
Apr 25 at 22:37
$begingroup$
@hexomino You're right! Fixed.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:26
$begingroup$
This is interesting, but to be honest, it doesn't actually answer the question as posed, I don't think.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
@Brandon_J is that really true? "You must determine the correct identities of all Ai's by asking questions, which have to be of one of the following forms: ... Can the number of questions be less than 2N, and if it can, what's the minimum number of questions needed?" The answer is that the minimum number of questions needed is determine the identities of all the islanders is 2. This isn't enough for all cases, but the question doesn't ask about all cases, does it? It only asks for the minimum.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:47
$begingroup$
@ArcanistLupus hmmm...I guess this is something to ask the OP. Usually problems like this are supposed to cover worst-case scenarios (i.e. only 1 knight and 1 spy), but he doesn't specify. I assumed convention, but I could be wrong.
$endgroup$
– Brandon_J
Apr 26 at 0:53
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "559"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f83179%2fisland-of-knights-knaves-and-spies%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It takes
at most about $5N/3$ questions.
Suppose
we know a knight or spy and want to find the identities of $k$ islanders. We can find the division of $k$ into knights, knaves, or spies by asking the knight/spy at most five questions of the second type. Suppose the most represented type is X. Then we ask the knight/spy whether each of the $k$ is X. This determines exactly which of them is X, so we can determine the remainder by asking the knight/spy whether each of them is one of the remaining types. In the worst case, each of the classes is equally represented among the $k$, so that this takes about $5k/3$ questions.
Now
our strategy is to find a knight/spy. First we use the known two question strategy to determine the identity of an islander. If they are a knave, we keep asking them whether other islanders are knaves. Each knave discovered in this way requires only one question, so in the worst case we quickly discover a knight/spy, and we use about $5N/3$ questions in total.
answered Apr 25 at 14:19
noednenoedne
9,93212769
$endgroup$
$begingroup$
It seems like there is a bit of a flaw: If we identify a spy, then we can't simply find which of the k are type X in k questions by asking the spy "is A_i of type X?" because we will get lies every other time. We are not allowed to ask "or" questions.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@BoltonBailey We know the truth/lie pattern, so we can just negate the lies.
$endgroup$
– noedne
2 days ago
$begingroup$
You can't just negate the lies. You are only allowed to ask questions of the given forms, not their negations.
$endgroup$
– Bolton Bailey
2 days ago
2
$begingroup$
@BoltonBailey Negate the answer, not the question.
$endgroup$
– noedne
2 days ago
$begingroup$
Yep. That works.
$endgroup$
– Bolton Bailey
2 days ago
|
show 5 more comments
$begingroup$
It takes
at most about $5N/3$ questions.
Suppose
we know a knight or spy and want to find the identities of $k$ islanders. We can find the division of $k$ into knights, knaves, or spies by asking the knight/spy at most five questions of the second type. Suppose the most represented type is X. Then we ask the knight/spy whether each of the $k$ is X. This determines exactly which of them is X, so we can determine the remainder by asking the knight/spy whether each of them is one of the remaining types. In the worst case, each of the classes is equally represented among the $k$, so that this takes about $5k/3$ questions.
Now
our strategy is to find a knight/spy. First we use the known two question strategy to determine the identity of an islander. If they are a knave, we keep asking them whether other islanders are knaves. Each knave discovered in this way requires only one question, so in the worst case we quickly discover a knight/spy, and we use about $5N/3$ questions in total.
answered Apr 25 at 14:19
noednenoedne
9,93212769
$endgroup$
$begingroup$
It seems like there is a bit of a flaw: If we identify a spy, then we can't simply find which of the k are type X in k questions by asking the spy "is A_i of type X?" because we will get lies every other time. We are not allowed to ask "or" questions.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@BoltonBailey We know the truth/lie pattern, so we can just negate the lies.
$endgroup$
– noedne
2 days ago
$begingroup$
You can't just negate the lies. You are only allowed to ask questions of the given forms, not their negations.
$endgroup$
– Bolton Bailey
2 days ago
2
$begingroup$
@BoltonBailey Negate the answer, not the question.
$endgroup$
– noedne
2 days ago
$begingroup$
Yep. That works.
$endgroup$
– Bolton Bailey
2 days ago
|
show 5 more comments
$begingroup$
It takes
at most about $5N/3$ questions.
Suppose
we know a knight or spy and want to find the identities of $k$ islanders. We can find the division of $k$ into knights, knaves, or spies by asking the knight/spy at most five questions of the second type. Suppose the most represented type is X. Then we ask the knight/spy whether each of the $k$ is X. This determines exactly which of them is X, so we can determine the remainder by asking the knight/spy whether each of them is one of the remaining types. In the worst case, each of the classes is equally represented among the $k$, so that this takes about $5k/3$ questions.
Now
our strategy is to find a knight/spy. First we use the known two question strategy to determine the identity of an islander. If they are a knave, we keep asking them whether other islanders are knaves. Each knave discovered in this way requires only one question, so in the worst case we quickly discover a knight/spy, and we use about $5N/3$ questions in total.
answered Apr 25 at 14:19
noednenoedne
9,93212769
$endgroup$
It takes
at most about $5N/3$ questions.
Suppose
we know a knight or spy and want to find the identities of $k$ islanders. We can find the division of $k$ into knights, knaves, or spies by asking the knight/spy at most five questions of the second type. Suppose the most represented type is X. Then we ask the knight/spy whether each of the $k$ is X. This determines exactly which of them is X, so we can determine the remainder by asking the knight/spy whether each of them is one of the remaining types. In the worst case, each of the classes is equally represented among the $k$, so that this takes about $5k/3$ questions.
Now
our strategy is to find a knight/spy. First we use the known two question strategy to determine the identity of an islander. If they are a knave, we keep asking them whether other islanders are knaves. Each knave discovered in this way requires only one question, so in the worst case we quickly discover a knight/spy, and we use about $5N/3$ questions in total.
answered Apr 25 at 14:19
noednenoedne
9,93212769
edited Apr 25 at 14:29
answered Apr 25 at 14:19
noednenoedne
9,93212769
answered Apr 25 at 14:19
noednenoedne
9,93212769
answered Apr 25 at 14:19
noednenoedne
9,93212769
9,93212769
$begingroup$
It seems like there is a bit of a flaw: If we identify a spy, then we can't simply find which of the k are type X in k questions by asking the spy "is A_i of type X?" because we will get lies every other time. We are not allowed to ask "or" questions.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@BoltonBailey We know the truth/lie pattern, so we can just negate the lies.
$endgroup$
– noedne
2 days ago
$begingroup$
You can't just negate the lies. You are only allowed to ask questions of the given forms, not their negations.
$endgroup$
– Bolton Bailey
2 days ago
2
$begingroup$
@BoltonBailey Negate the answer, not the question.
$endgroup$
– noedne
2 days ago
$begingroup$
Yep. That works.
$endgroup$
– Bolton Bailey
2 days ago
|
show 5 more comments
$begingroup$
It seems like there is a bit of a flaw: If we identify a spy, then we can't simply find which of the k are type X in k questions by asking the spy "is A_i of type X?" because we will get lies every other time. We are not allowed to ask "or" questions.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@BoltonBailey We know the truth/lie pattern, so we can just negate the lies.
$endgroup$
– noedne
2 days ago
$begingroup$
You can't just negate the lies. You are only allowed to ask questions of the given forms, not their negations.
$endgroup$
– Bolton Bailey
2 days ago
2
$begingroup$
@BoltonBailey Negate the answer, not the question.
$endgroup$
– noedne
2 days ago
$begingroup$
Yep. That works.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
It seems like there is a bit of a flaw: If we identify a spy, then we can't simply find which of the k are type X in k questions by asking the spy "is A_i of type X?" because we will get lies every other time. We are not allowed to ask "or" questions.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
It seems like there is a bit of a flaw: If we identify a spy, then we can't simply find which of the k are type X in k questions by asking the spy "is A_i of type X?" because we will get lies every other time. We are not allowed to ask "or" questions.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@BoltonBailey We know the truth/lie pattern, so we can just negate the lies.
$endgroup$
– noedne
2 days ago
$begingroup$
@BoltonBailey We know the truth/lie pattern, so we can just negate the lies.
$endgroup$
– noedne
2 days ago
$begingroup$
You can't just negate the lies. You are only allowed to ask questions of the given forms, not their negations.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
You can't just negate the lies. You are only allowed to ask questions of the given forms, not their negations.
$endgroup$
– Bolton Bailey
2 days ago
2
2
$begingroup$
@BoltonBailey Negate the answer, not the question.
$endgroup$
– noedne
2 days ago
$begingroup$
@BoltonBailey Negate the answer, not the question.
$endgroup$
– noedne
2 days ago
$begingroup$
Yep. That works.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
Yep. That works.
$endgroup$
– Bolton Bailey
2 days ago
|
show 5 more comments
$begingroup$
Assuming inhabitants know the identity of other inhabitants and a bit of math, for N inhabitants, I believe you could find the identity of every inhabitant with a number of questions approximately equal to
$3 + frac(N - 1) * log(3)log(2)$
Here's how:
Take aside one inhabitant and figure out, using the 2 questions in the
question to determine whether the inhabitant is a knight, a knave or a
spy.
.
If faced with a spy, ask, as a third question, whether or not he or
she is a spy. This will tell you which "phase" the spy is in, allowing
you to determine the truth value of future answers. If the spy says he
is not a spy, then that is a lie, and his next answer will be the
truth. If the spy admits to being a spy, his next answer will be a
lie, and so on.
.
You now have one person you can use to find out the true answer to any
question. (Taking the negation if you have a knave) Let's hope this
person is patient and knows a bit of math. You will be asking him a
series of questions.
.
You will line up all of the other N-1 inhabitants and ask the
inhabitant whose identity has been determined to compute a trinary
number where each trinary digit corresponds to one of the other N-1
inhabitants: 0 if the inhabitant is a knight, 1 if a knave and 2 if a
spy. For a trinary number with N-1 digits, there are $3^N-1$
possibilities.
A binary search will then allow you to eliminate half of these
possibilities with a single question, repeating until there is only
one option.
answered Apr 25 at 19:24
Vincent B. LortieVincent B. Lortie
312
New contributor
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Could you elaborate on your last paragraph? I'm not convinced that a binary search is possible under the restrictions of the questions - how would it be done?
$endgroup$
– hexomino
Apr 25 at 19:55
$begingroup$
That being said, this answer is pretty useful as I think it provides a lower bound. It's pretty close to noedne's answer which makes me think that is the best that could be achieved.
$endgroup$
– hexomino
Apr 25 at 20:00
$begingroup$
@hexomino We know both the biggest and smallest possible N-digit trinary numbers: N^3-1 and 0. Take the halfway point, ask if the number I described in my answer is greater or lesser than, then repeat on the reduced range.
$endgroup$
– Vincent B. Lortie
Apr 26 at 2:17
1
$begingroup$
It's not clear to me that this question about the trinary number can be asked in the form of one of the two questions types allowed.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@VincentB.Lortie Yes, I agree with what Bolton Bailey says, you are only permitted to ask either "Is A_i a knight/knave/spy?" or "How many among you are knights/knaves/spies?" You are not permitted to ask questions about a trinary number.
$endgroup$
– hexomino
2 days ago
add a comment |
$begingroup$
Assuming inhabitants know the identity of other inhabitants and a bit of math, for N inhabitants, I believe you could find the identity of every inhabitant with a number of questions approximately equal to
$3 + frac(N - 1) * log(3)log(2)$
Here's how:
Take aside one inhabitant and figure out, using the 2 questions in the
question to determine whether the inhabitant is a knight, a knave or a
spy.
.
If faced with a spy, ask, as a third question, whether or not he or
she is a spy. This will tell you which "phase" the spy is in, allowing
you to determine the truth value of future answers. If the spy says he
is not a spy, then that is a lie, and his next answer will be the
truth. If the spy admits to being a spy, his next answer will be a
lie, and so on.
.
You now have one person you can use to find out the true answer to any
question. (Taking the negation if you have a knave) Let's hope this
person is patient and knows a bit of math. You will be asking him a
series of questions.
.
You will line up all of the other N-1 inhabitants and ask the
inhabitant whose identity has been determined to compute a trinary
number where each trinary digit corresponds to one of the other N-1
inhabitants: 0 if the inhabitant is a knight, 1 if a knave and 2 if a
spy. For a trinary number with N-1 digits, there are $3^N-1$
possibilities.
A binary search will then allow you to eliminate half of these
possibilities with a single question, repeating until there is only
one option.
answered Apr 25 at 19:24
Vincent B. LortieVincent B. Lortie
312
New contributor
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Could you elaborate on your last paragraph? I'm not convinced that a binary search is possible under the restrictions of the questions - how would it be done?
$endgroup$
– hexomino
Apr 25 at 19:55
$begingroup$
That being said, this answer is pretty useful as I think it provides a lower bound. It's pretty close to noedne's answer which makes me think that is the best that could be achieved.
$endgroup$
– hexomino
Apr 25 at 20:00
$begingroup$
@hexomino We know both the biggest and smallest possible N-digit trinary numbers: N^3-1 and 0. Take the halfway point, ask if the number I described in my answer is greater or lesser than, then repeat on the reduced range.
$endgroup$
– Vincent B. Lortie
Apr 26 at 2:17
1
$begingroup$
It's not clear to me that this question about the trinary number can be asked in the form of one of the two questions types allowed.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@VincentB.Lortie Yes, I agree with what Bolton Bailey says, you are only permitted to ask either "Is A_i a knight/knave/spy?" or "How many among you are knights/knaves/spies?" You are not permitted to ask questions about a trinary number.
$endgroup$
– hexomino
2 days ago
add a comment |
$begingroup$
Assuming inhabitants know the identity of other inhabitants and a bit of math, for N inhabitants, I believe you could find the identity of every inhabitant with a number of questions approximately equal to
$3 + frac(N - 1) * log(3)log(2)$
Here's how:
Take aside one inhabitant and figure out, using the 2 questions in the
question to determine whether the inhabitant is a knight, a knave or a
spy.
.
If faced with a spy, ask, as a third question, whether or not he or
she is a spy. This will tell you which "phase" the spy is in, allowing
you to determine the truth value of future answers. If the spy says he
is not a spy, then that is a lie, and his next answer will be the
truth. If the spy admits to being a spy, his next answer will be a
lie, and so on.
.
You now have one person you can use to find out the true answer to any
question. (Taking the negation if you have a knave) Let's hope this
person is patient and knows a bit of math. You will be asking him a
series of questions.
.
You will line up all of the other N-1 inhabitants and ask the
inhabitant whose identity has been determined to compute a trinary
number where each trinary digit corresponds to one of the other N-1
inhabitants: 0 if the inhabitant is a knight, 1 if a knave and 2 if a
spy. For a trinary number with N-1 digits, there are $3^N-1$
possibilities.
A binary search will then allow you to eliminate half of these
possibilities with a single question, repeating until there is only
one option.
answered Apr 25 at 19:24
Vincent B. LortieVincent B. Lortie
312
New contributor
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Assuming inhabitants know the identity of other inhabitants and a bit of math, for N inhabitants, I believe you could find the identity of every inhabitant with a number of questions approximately equal to
$3 + frac(N - 1) * log(3)log(2)$
Here's how:
Take aside one inhabitant and figure out, using the 2 questions in the
question to determine whether the inhabitant is a knight, a knave or a
spy.
.
If faced with a spy, ask, as a third question, whether or not he or
she is a spy. This will tell you which "phase" the spy is in, allowing
you to determine the truth value of future answers. If the spy says he
is not a spy, then that is a lie, and his next answer will be the
truth. If the spy admits to being a spy, his next answer will be a
lie, and so on.
.
You now have one person you can use to find out the true answer to any
question. (Taking the negation if you have a knave) Let's hope this
person is patient and knows a bit of math. You will be asking him a
series of questions.
.
You will line up all of the other N-1 inhabitants and ask the
inhabitant whose identity has been determined to compute a trinary
number where each trinary digit corresponds to one of the other N-1
inhabitants: 0 if the inhabitant is a knight, 1 if a knave and 2 if a
spy. For a trinary number with N-1 digits, there are $3^N-1$
possibilities.
A binary search will then allow you to eliminate half of these
possibilities with a single question, repeating until there is only
one option.
answered Apr 25 at 19:24
Vincent B. LortieVincent B. Lortie
312
New contributor
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Apr 25 at 19:33
answered Apr 25 at 19:24
Vincent B. LortieVincent B. Lortie
312
New contributor
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Apr 25 at 19:24
Vincent B. LortieVincent B. Lortie
312
answered Apr 25 at 19:24
Vincent B. LortieVincent B. Lortie
312
312
New contributor
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Vincent B. Lortie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
Could you elaborate on your last paragraph? I'm not convinced that a binary search is possible under the restrictions of the questions - how would it be done?
$endgroup$
– hexomino
Apr 25 at 19:55
$begingroup$
That being said, this answer is pretty useful as I think it provides a lower bound. It's pretty close to noedne's answer which makes me think that is the best that could be achieved.
$endgroup$
– hexomino
Apr 25 at 20:00
$begingroup$
@hexomino We know both the biggest and smallest possible N-digit trinary numbers: N^3-1 and 0. Take the halfway point, ask if the number I described in my answer is greater or lesser than, then repeat on the reduced range.
$endgroup$
– Vincent B. Lortie
Apr 26 at 2:17
1
$begingroup$
It's not clear to me that this question about the trinary number can be asked in the form of one of the two questions types allowed.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@VincentB.Lortie Yes, I agree with what Bolton Bailey says, you are only permitted to ask either "Is A_i a knight/knave/spy?" or "How many among you are knights/knaves/spies?" You are not permitted to ask questions about a trinary number.
$endgroup$
– hexomino
2 days ago
add a comment |
1
$begingroup$
Could you elaborate on your last paragraph? I'm not convinced that a binary search is possible under the restrictions of the questions - how would it be done?
$endgroup$
– hexomino
Apr 25 at 19:55
$begingroup$
That being said, this answer is pretty useful as I think it provides a lower bound. It's pretty close to noedne's answer which makes me think that is the best that could be achieved.
$endgroup$
– hexomino
Apr 25 at 20:00
$begingroup$
@hexomino We know both the biggest and smallest possible N-digit trinary numbers: N^3-1 and 0. Take the halfway point, ask if the number I described in my answer is greater or lesser than, then repeat on the reduced range.
$endgroup$
– Vincent B. Lortie
Apr 26 at 2:17
1
$begingroup$
It's not clear to me that this question about the trinary number can be asked in the form of one of the two questions types allowed.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@VincentB.Lortie Yes, I agree with what Bolton Bailey says, you are only permitted to ask either "Is A_i a knight/knave/spy?" or "How many among you are knights/knaves/spies?" You are not permitted to ask questions about a trinary number.
$endgroup$
– hexomino
2 days ago
1
1
$begingroup$
Could you elaborate on your last paragraph? I'm not convinced that a binary search is possible under the restrictions of the questions - how would it be done?
$endgroup$
– hexomino
Apr 25 at 19:55
$begingroup$
Could you elaborate on your last paragraph? I'm not convinced that a binary search is possible under the restrictions of the questions - how would it be done?
$endgroup$
– hexomino
Apr 25 at 19:55
$begingroup$
That being said, this answer is pretty useful as I think it provides a lower bound. It's pretty close to noedne's answer which makes me think that is the best that could be achieved.
$endgroup$
– hexomino
Apr 25 at 20:00
$begingroup$
That being said, this answer is pretty useful as I think it provides a lower bound. It's pretty close to noedne's answer which makes me think that is the best that could be achieved.
$endgroup$
– hexomino
Apr 25 at 20:00
$begingroup$
@hexomino We know both the biggest and smallest possible N-digit trinary numbers: N^3-1 and 0. Take the halfway point, ask if the number I described in my answer is greater or lesser than, then repeat on the reduced range.
$endgroup$
– Vincent B. Lortie
Apr 26 at 2:17
$begingroup$
@hexomino We know both the biggest and smallest possible N-digit trinary numbers: N^3-1 and 0. Take the halfway point, ask if the number I described in my answer is greater or lesser than, then repeat on the reduced range.
$endgroup$
– Vincent B. Lortie
Apr 26 at 2:17
1
1
$begingroup$
It's not clear to me that this question about the trinary number can be asked in the form of one of the two questions types allowed.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
It's not clear to me that this question about the trinary number can be asked in the form of one of the two questions types allowed.
$endgroup$
– Bolton Bailey
2 days ago
$begingroup$
@VincentB.Lortie Yes, I agree with what Bolton Bailey says, you are only permitted to ask either "Is A_i a knight/knave/spy?" or "How many among you are knights/knaves/spies?" You are not permitted to ask questions about a trinary number.
$endgroup$
– hexomino
2 days ago
$begingroup$
@VincentB.Lortie Yes, I agree with what Bolton Bailey says, you are only permitted to ask either "Is A_i a knight/knave/spy?" or "How many among you are knights/knaves/spies?" You are not permitted to ask questions about a trinary number.
$endgroup$
– hexomino
2 days ago
add a comment |
$begingroup$
Some upper bounds on the number of questions needed have been provided. Here is a lower bound:
Based on information theory. Suppose that $N = 3k$ and that before our interrogation, we are told that the true number of knights, knaves and spies are each $k$. Thus, asking questions of the second kind is equivalent to querying whether a individual is telling the truth this round. This imparts 1 bit of information. Similarly, questions of the first kind impart 1 bit of information, because they are Yes/No questions. Since the total number of possibilities is $binom3kk,k,k ge (3k/k)^k(2k/k)^k = 6^k$, we will still need $log_2 6^k = k log_2 6 = N frac13 log_2 6 approx N * 0.86$
answered 2 days ago
Bolton BaileyBolton Bailey
1314
New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Some upper bounds on the number of questions needed have been provided. Here is a lower bound:
Based on information theory. Suppose that $N = 3k$ and that before our interrogation, we are told that the true number of knights, knaves and spies are each $k$. Thus, asking questions of the second kind is equivalent to querying whether a individual is telling the truth this round. This imparts 1 bit of information. Similarly, questions of the first kind impart 1 bit of information, because they are Yes/No questions. Since the total number of possibilities is $binom3kk,k,k ge (3k/k)^k(2k/k)^k = 6^k$, we will still need $log_2 6^k = k log_2 6 = N frac13 log_2 6 approx N * 0.86$
answered 2 days ago
Bolton BaileyBolton Bailey
1314
New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Some upper bounds on the number of questions needed have been provided. Here is a lower bound:
Based on information theory. Suppose that $N = 3k$ and that before our interrogation, we are told that the true number of knights, knaves and spies are each $k$. Thus, asking questions of the second kind is equivalent to querying whether a individual is telling the truth this round. This imparts 1 bit of information. Similarly, questions of the first kind impart 1 bit of information, because they are Yes/No questions. Since the total number of possibilities is $binom3kk,k,k ge (3k/k)^k(2k/k)^k = 6^k$, we will still need $log_2 6^k = k log_2 6 = N frac13 log_2 6 approx N * 0.86$
answered 2 days ago
Bolton BaileyBolton Bailey
1314
New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Some upper bounds on the number of questions needed have been provided. Here is a lower bound:
Based on information theory. Suppose that $N = 3k$ and that before our interrogation, we are told that the true number of knights, knaves and spies are each $k$. Thus, asking questions of the second kind is equivalent to querying whether a individual is telling the truth this round. This imparts 1 bit of information. Similarly, questions of the first kind impart 1 bit of information, because they are Yes/No questions. Since the total number of possibilities is $binom3kk,k,k ge (3k/k)^k(2k/k)^k = 6^k$, we will still need $log_2 6^k = k log_2 6 = N frac13 log_2 6 approx N * 0.86$
answered 2 days ago
Bolton BaileyBolton Bailey
1314
New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 days ago
Bolton BaileyBolton Bailey
1314
New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 days ago
Bolton BaileyBolton Bailey
1314
answered 2 days ago
Bolton BaileyBolton Bailey
1314
1314
New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
$begingroup$
Wrong answer
[EDITED to add:] Oops, the following is all wrong; thanks to @hexomino for pointing out in comments that I misinterpreted the question. I'm leaving this here rather than deleting it because (1) it's possible that some idea in it is salvageable and (2) I don't believe in making myself look better by deleting my mistakes :-). (I might delete it later to reduce clutter.)
The minimal number of questions
is less than $2N$, at least when $N$ is not too small. In fact, it's never more than $frac43N$ plus a few.
Here's why.
First, use two "are you a spy?" questions to establish what #1 is, and also (if they're a spy) which way around their truth-telling and lying answers are. We now have three cases. If #1 is a knight then we can just ask them about everyone else, and we're done in $N+1$ questions. If #1 is a spy then we ask them about everyone else -- once, asking "what is X?", when they are telling the truth, and twice, asking binary questions, when they are lying. Every 4 questions we find out about 3 people, so we take approximately $frac43N$ questions.
The hardest case is when #1 is a knave. Here's one way to proceed. Ask them "is X a knave?" about each other person in turn. If they say "no" then we have correctly identified that X is a knave, and if that's all that ever happens then again we're done in $N+1$ questions. If at some point they say "yes" then we have found a non-knave. We can then ask that person two questions to figure out exactly what they are and (if they're a spy) what their "phase" is, and then proceed as above, asking them about everyone else in turn.
In the worst case: we take two questions to establish that #1 is a knave; we take one more question to establish that #2 is knot a knave; we take two questions to establish that #2 is a spy and phind his phase; we then have $N-2$ people to figure out, divide them into $leftlceilfracN-23rightrceil$ groups of at most 3, and use 4 questions for each group, for a total of $leftlceilfracN-23rightrceil+5$ questions. I make no claim that this is optimal, though.
answered Apr 25 at 13:57
Gareth McCaughan♦Gareth McCaughan
68.7k3174269
$endgroup$
2
$begingroup$
I think if #1 is a knight we still need 2N-2 questions because you can only ask questions like "Is A_j a knight?" not "What is A_j?" meaning that in the worst case you would still need two questions to determine each one, right?
$endgroup$
– hexomino
Apr 25 at 14:02
$begingroup$
oh, damn, I misread the question. You're right; we don't get to ask "what is X?" questions at all.
$endgroup$
– Gareth McCaughan♦
Apr 25 at 14:03
add a comment |
$begingroup$
Wrong answer
[EDITED to add:] Oops, the following is all wrong; thanks to @hexomino for pointing out in comments that I misinterpreted the question. I'm leaving this here rather than deleting it because (1) it's possible that some idea in it is salvageable and (2) I don't believe in making myself look better by deleting my mistakes :-). (I might delete it later to reduce clutter.)
The minimal number of questions
is less than $2N$, at least when $N$ is not too small. In fact, it's never more than $frac43N$ plus a few.
Here's why.
First, use two "are you a spy?" questions to establish what #1 is, and also (if they're a spy) which way around their truth-telling and lying answers are. We now have three cases. If #1 is a knight then we can just ask them about everyone else, and we're done in $N+1$ questions. If #1 is a spy then we ask them about everyone else -- once, asking "what is X?", when they are telling the truth, and twice, asking binary questions, when they are lying. Every 4 questions we find out about 3 people, so we take approximately $frac43N$ questions.
The hardest case is when #1 is a knave. Here's one way to proceed. Ask them "is X a knave?" about each other person in turn. If they say "no" then we have correctly identified that X is a knave, and if that's all that ever happens then again we're done in $N+1$ questions. If at some point they say "yes" then we have found a non-knave. We can then ask that person two questions to figure out exactly what they are and (if they're a spy) what their "phase" is, and then proceed as above, asking them about everyone else in turn.
In the worst case: we take two questions to establish that #1 is a knave; we take one more question to establish that #2 is knot a knave; we take two questions to establish that #2 is a spy and phind his phase; we then have $N-2$ people to figure out, divide them into $leftlceilfracN-23rightrceil$ groups of at most 3, and use 4 questions for each group, for a total of $leftlceilfracN-23rightrceil+5$ questions. I make no claim that this is optimal, though.
answered Apr 25 at 13:57
Gareth McCaughan♦Gareth McCaughan
68.7k3174269
$endgroup$
2
$begingroup$
I think if #1 is a knight we still need 2N-2 questions because you can only ask questions like "Is A_j a knight?" not "What is A_j?" meaning that in the worst case you would still need two questions to determine each one, right?
$endgroup$
– hexomino
Apr 25 at 14:02
$begingroup$
oh, damn, I misread the question. You're right; we don't get to ask "what is X?" questions at all.
$endgroup$
– Gareth McCaughan♦
Apr 25 at 14:03
add a comment |
$begingroup$
Wrong answer
[EDITED to add:] Oops, the following is all wrong; thanks to @hexomino for pointing out in comments that I misinterpreted the question. I'm leaving this here rather than deleting it because (1) it's possible that some idea in it is salvageable and (2) I don't believe in making myself look better by deleting my mistakes :-). (I might delete it later to reduce clutter.)
The minimal number of questions
is less than $2N$, at least when $N$ is not too small. In fact, it's never more than $frac43N$ plus a few.
Here's why.
First, use two "are you a spy?" questions to establish what #1 is, and also (if they're a spy) which way around their truth-telling and lying answers are. We now have three cases. If #1 is a knight then we can just ask them about everyone else, and we're done in $N+1$ questions. If #1 is a spy then we ask them about everyone else -- once, asking "what is X?", when they are telling the truth, and twice, asking binary questions, when they are lying. Every 4 questions we find out about 3 people, so we take approximately $frac43N$ questions.
The hardest case is when #1 is a knave. Here's one way to proceed. Ask them "is X a knave?" about each other person in turn. If they say "no" then we have correctly identified that X is a knave, and if that's all that ever happens then again we're done in $N+1$ questions. If at some point they say "yes" then we have found a non-knave. We can then ask that person two questions to figure out exactly what they are and (if they're a spy) what their "phase" is, and then proceed as above, asking them about everyone else in turn.
In the worst case: we take two questions to establish that #1 is a knave; we take one more question to establish that #2 is knot a knave; we take two questions to establish that #2 is a spy and phind his phase; we then have $N-2$ people to figure out, divide them into $leftlceilfracN-23rightrceil$ groups of at most 3, and use 4 questions for each group, for a total of $leftlceilfracN-23rightrceil+5$ questions. I make no claim that this is optimal, though.
answered Apr 25 at 13:57
Gareth McCaughan♦Gareth McCaughan
68.7k3174269
$endgroup$
Wrong answer
[EDITED to add:] Oops, the following is all wrong; thanks to @hexomino for pointing out in comments that I misinterpreted the question. I'm leaving this here rather than deleting it because (1) it's possible that some idea in it is salvageable and (2) I don't believe in making myself look better by deleting my mistakes :-). (I might delete it later to reduce clutter.)
The minimal number of questions
is less than $2N$, at least when $N$ is not too small. In fact, it's never more than $frac43N$ plus a few.
Here's why.
First, use two "are you a spy?" questions to establish what #1 is, and also (if they're a spy) which way around their truth-telling and lying answers are. We now have three cases. If #1 is a knight then we can just ask them about everyone else, and we're done in $N+1$ questions. If #1 is a spy then we ask them about everyone else -- once, asking "what is X?", when they are telling the truth, and twice, asking binary questions, when they are lying. Every 4 questions we find out about 3 people, so we take approximately $frac43N$ questions.
The hardest case is when #1 is a knave. Here's one way to proceed. Ask them "is X a knave?" about each other person in turn. If they say "no" then we have correctly identified that X is a knave, and if that's all that ever happens then again we're done in $N+1$ questions. If at some point they say "yes" then we have found a non-knave. We can then ask that person two questions to figure out exactly what they are and (if they're a spy) what their "phase" is, and then proceed as above, asking them about everyone else in turn.
In the worst case: we take two questions to establish that #1 is a knave; we take one more question to establish that #2 is knot a knave; we take two questions to establish that #2 is a spy and phind his phase; we then have $N-2$ people to figure out, divide them into $leftlceilfracN-23rightrceil$ groups of at most 3, and use 4 questions for each group, for a total of $leftlceilfracN-23rightrceil+5$ questions. I make no claim that this is optimal, though.
answered Apr 25 at 13:57
Gareth McCaughan♦Gareth McCaughan
68.7k3174269
edited Apr 25 at 14:03
answered Apr 25 at 13:57
Gareth McCaughan♦Gareth McCaughan
68.7k3174269
answered Apr 25 at 13:57
Gareth McCaughan♦Gareth McCaughan
68.7k3174269
answered Apr 25 at 13:57
Gareth McCaughan♦Gareth McCaughan
68.7k3174269
68.7k3174269
2
$begingroup$
I think if #1 is a knight we still need 2N-2 questions because you can only ask questions like "Is A_j a knight?" not "What is A_j?" meaning that in the worst case you would still need two questions to determine each one, right?
$endgroup$
– hexomino
Apr 25 at 14:02
$begingroup$
oh, damn, I misread the question. You're right; we don't get to ask "what is X?" questions at all.
$endgroup$
– Gareth McCaughan♦
Apr 25 at 14:03
add a comment |
2
$begingroup$
I think if #1 is a knight we still need 2N-2 questions because you can only ask questions like "Is A_j a knight?" not "What is A_j?" meaning that in the worst case you would still need two questions to determine each one, right?
$endgroup$
– hexomino
Apr 25 at 14:02
$begingroup$
oh, damn, I misread the question. You're right; we don't get to ask "what is X?" questions at all.
$endgroup$
– Gareth McCaughan♦
Apr 25 at 14:03
2
2
$begingroup$
I think if #1 is a knight we still need 2N-2 questions because you can only ask questions like "Is A_j a knight?" not "What is A_j?" meaning that in the worst case you would still need two questions to determine each one, right?
$endgroup$
– hexomino
Apr 25 at 14:02
$begingroup$
I think if #1 is a knight we still need 2N-2 questions because you can only ask questions like "Is A_j a knight?" not "What is A_j?" meaning that in the worst case you would still need two questions to determine each one, right?
$endgroup$
– hexomino
Apr 25 at 14:02
$begingroup$
oh, damn, I misread the question. You're right; we don't get to ask "what is X?" questions at all.
$endgroup$
– Gareth McCaughan♦
Apr 25 at 14:03
$begingroup$
oh, damn, I misread the question. You're right; we don't get to ask "what is X?" questions at all.
$endgroup$
– Gareth McCaughan♦
Apr 25 at 14:03
add a comment |
$begingroup$
The minimum number of questions needed is
2, but only if you're lucky
How?
You ask the first person:
"Are you a spy?"
"No."
"How many knights are there?"
"N"
After the first question, they're either a knight or a lying spy. Either way, the next answer will be truthful. And since that truthful answer indicated that everyone is a knight, clearly they're also a knight.
And you're done! They're all knights!
answered Apr 25 at 21:02
Arcanist LupusArcanist Lupus
42218
$endgroup$
1
$begingroup$
This can actually be reduced to two questions, if you're very lucky. Can you see how? This interpretation, in itself, is a good mini-puzzle.
$endgroup$
– hexomino
Apr 25 at 22:37
$begingroup$
@hexomino You're right! Fixed.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:26
$begingroup$
This is interesting, but to be honest, it doesn't actually answer the question as posed, I don't think.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
@Brandon_J is that really true? "You must determine the correct identities of all Ai's by asking questions, which have to be of one of the following forms: ... Can the number of questions be less than 2N, and if it can, what's the minimum number of questions needed?" The answer is that the minimum number of questions needed is determine the identities of all the islanders is 2. This isn't enough for all cases, but the question doesn't ask about all cases, does it? It only asks for the minimum.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:47
$begingroup$
@ArcanistLupus hmmm...I guess this is something to ask the OP. Usually problems like this are supposed to cover worst-case scenarios (i.e. only 1 knight and 1 spy), but he doesn't specify. I assumed convention, but I could be wrong.
$endgroup$
– Brandon_J
Apr 26 at 0:53
add a comment |
$begingroup$
The minimum number of questions needed is
2, but only if you're lucky
How?
You ask the first person:
"Are you a spy?"
"No."
"How many knights are there?"
"N"
After the first question, they're either a knight or a lying spy. Either way, the next answer will be truthful. And since that truthful answer indicated that everyone is a knight, clearly they're also a knight.
And you're done! They're all knights!
answered Apr 25 at 21:02
Arcanist LupusArcanist Lupus
42218
$endgroup$
1
$begingroup$
This can actually be reduced to two questions, if you're very lucky. Can you see how? This interpretation, in itself, is a good mini-puzzle.
$endgroup$
– hexomino
Apr 25 at 22:37
$begingroup$
@hexomino You're right! Fixed.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:26
$begingroup$
This is interesting, but to be honest, it doesn't actually answer the question as posed, I don't think.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
@Brandon_J is that really true? "You must determine the correct identities of all Ai's by asking questions, which have to be of one of the following forms: ... Can the number of questions be less than 2N, and if it can, what's the minimum number of questions needed?" The answer is that the minimum number of questions needed is determine the identities of all the islanders is 2. This isn't enough for all cases, but the question doesn't ask about all cases, does it? It only asks for the minimum.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:47
$begingroup$
@ArcanistLupus hmmm...I guess this is something to ask the OP. Usually problems like this are supposed to cover worst-case scenarios (i.e. only 1 knight and 1 spy), but he doesn't specify. I assumed convention, but I could be wrong.
$endgroup$
– Brandon_J
Apr 26 at 0:53
add a comment |
$begingroup$
The minimum number of questions needed is
2, but only if you're lucky
How?
You ask the first person:
"Are you a spy?"
"No."
"How many knights are there?"
"N"
After the first question, they're either a knight or a lying spy. Either way, the next answer will be truthful. And since that truthful answer indicated that everyone is a knight, clearly they're also a knight.
And you're done! They're all knights!
answered Apr 25 at 21:02
Arcanist LupusArcanist Lupus
42218
$endgroup$
The minimum number of questions needed is
2, but only if you're lucky
How?
You ask the first person:
"Are you a spy?"
"No."
"How many knights are there?"
"N"
After the first question, they're either a knight or a lying spy. Either way, the next answer will be truthful. And since that truthful answer indicated that everyone is a knight, clearly they're also a knight.
And you're done! They're all knights!
answered Apr 25 at 21:02
Arcanist LupusArcanist Lupus
42218
edited Apr 26 at 0:27
answered Apr 25 at 21:02
Arcanist LupusArcanist Lupus
42218
answered Apr 25 at 21:02
Arcanist LupusArcanist Lupus
42218
answered Apr 25 at 21:02
Arcanist LupusArcanist Lupus
42218
42218
1
$begingroup$
This can actually be reduced to two questions, if you're very lucky. Can you see how? This interpretation, in itself, is a good mini-puzzle.
$endgroup$
– hexomino
Apr 25 at 22:37
$begingroup$
@hexomino You're right! Fixed.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:26
$begingroup$
This is interesting, but to be honest, it doesn't actually answer the question as posed, I don't think.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
@Brandon_J is that really true? "You must determine the correct identities of all Ai's by asking questions, which have to be of one of the following forms: ... Can the number of questions be less than 2N, and if it can, what's the minimum number of questions needed?" The answer is that the minimum number of questions needed is determine the identities of all the islanders is 2. This isn't enough for all cases, but the question doesn't ask about all cases, does it? It only asks for the minimum.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:47
$begingroup$
@ArcanistLupus hmmm...I guess this is something to ask the OP. Usually problems like this are supposed to cover worst-case scenarios (i.e. only 1 knight and 1 spy), but he doesn't specify. I assumed convention, but I could be wrong.
$endgroup$
– Brandon_J
Apr 26 at 0:53
add a comment |
1
$begingroup$
This can actually be reduced to two questions, if you're very lucky. Can you see how? This interpretation, in itself, is a good mini-puzzle.
$endgroup$
– hexomino
Apr 25 at 22:37
$begingroup$
@hexomino You're right! Fixed.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:26
$begingroup$
This is interesting, but to be honest, it doesn't actually answer the question as posed, I don't think.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
@Brandon_J is that really true? "You must determine the correct identities of all Ai's by asking questions, which have to be of one of the following forms: ... Can the number of questions be less than 2N, and if it can, what's the minimum number of questions needed?" The answer is that the minimum number of questions needed is determine the identities of all the islanders is 2. This isn't enough for all cases, but the question doesn't ask about all cases, does it? It only asks for the minimum.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:47
$begingroup$
@ArcanistLupus hmmm...I guess this is something to ask the OP. Usually problems like this are supposed to cover worst-case scenarios (i.e. only 1 knight and 1 spy), but he doesn't specify. I assumed convention, but I could be wrong.
$endgroup$
– Brandon_J
Apr 26 at 0:53
1
1
$begingroup$
This can actually be reduced to two questions, if you're very lucky. Can you see how? This interpretation, in itself, is a good mini-puzzle.
$endgroup$
– hexomino
Apr 25 at 22:37
$begingroup$
This can actually be reduced to two questions, if you're very lucky. Can you see how? This interpretation, in itself, is a good mini-puzzle.
$endgroup$
– hexomino
Apr 25 at 22:37
$begingroup$
@hexomino You're right! Fixed.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:26
$begingroup$
@hexomino You're right! Fixed.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:26
$begingroup$
This is interesting, but to be honest, it doesn't actually answer the question as posed, I don't think.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
This is interesting, but to be honest, it doesn't actually answer the question as posed, I don't think.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
@Brandon_J is that really true? "You must determine the correct identities of all Ai's by asking questions, which have to be of one of the following forms: ... Can the number of questions be less than 2N, and if it can, what's the minimum number of questions needed?" The answer is that the minimum number of questions needed is determine the identities of all the islanders is 2. This isn't enough for all cases, but the question doesn't ask about all cases, does it? It only asks for the minimum.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:47
$begingroup$
@Brandon_J is that really true? "You must determine the correct identities of all Ai's by asking questions, which have to be of one of the following forms: ... Can the number of questions be less than 2N, and if it can, what's the minimum number of questions needed?" The answer is that the minimum number of questions needed is determine the identities of all the islanders is 2. This isn't enough for all cases, but the question doesn't ask about all cases, does it? It only asks for the minimum.
$endgroup$
– Arcanist Lupus
Apr 26 at 0:47
$begingroup$
@ArcanistLupus hmmm...I guess this is something to ask the OP. Usually problems like this are supposed to cover worst-case scenarios (i.e. only 1 knight and 1 spy), but he doesn't specify. I assumed convention, but I could be wrong.
$endgroup$
– Brandon_J
Apr 26 at 0:53
$begingroup$
@ArcanistLupus hmmm...I guess this is something to ask the OP. Usually problems like this are supposed to cover worst-case scenarios (i.e. only 1 knight and 1 spy), but he doesn't specify. I assumed convention, but I could be wrong.
$endgroup$
– Brandon_J
Apr 26 at 0:53
add a comment |
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f83179%2fisland-of-knights-knaves-and-spies%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I take it we should assume that all the islanders know what everyone is?
$endgroup$
– Gareth McCaughan♦
Apr 25 at 11:13
$begingroup$
I assume you are looking for a strategy that guarantees that you will know the identity of every islander with fewer than 2N questions even in the worst case. Correct?
$endgroup$
– Hugh Meyers
Apr 25 at 13:22
$begingroup$
... and if so, then I suppose the worst case has to be that everyone is a knave thus making the second question valueless.
$endgroup$
– Hugh Meyers
Apr 25 at 13:27
6
$begingroup$
Can I subdivide groups? For example, If I split off a group of M < N and ask the second question, will they respond (0..M) or (0..N)?
$endgroup$
– Chris Cudmore
Apr 25 at 14:28
$begingroup$
@GarethMcCaughan Thanks for noticing! I've done some clarifications.
$endgroup$
– trolley813
2 days ago