5
$\begingroup$

A traveller visited one of the islands described by Raymond Smullyan on which all inhabitants are either knights, who always tell the truth, knaves, who always lie, or normals, who can say anything.

The traveller met three inhabitants: A, B, and C. He knew that one of the three was a knight, one a knave, and one normal, so there were six possibilities to distinguish between: "A is a knight, B is a knave, and C is normal", "A is a knight, B is normal, and C is a knave", and so on. He picked a subset $S$ of this set of six possibilities, and asked A whether $S$ contained the correct possibility. A answered yes or no, but the answer did not give the traveller enough information to rule out the possibility that A was a knight, or the possibility that A was a knave, or the possibility that A was normal.

The traveller then asked B what type C was. B answered, saying either "C is a knight", "C is a knave", or "C is normal", and the traveller then had enough information to deduce the types of all three inhabitants.

I apologise for not precisely remembering $S$, or the answers given by A and B. What type was A?

$\endgroup$
2
  • $\begingroup$ This is confusing. Do you really apologies or figuring out what is S and answers of A and B is part of the puzzle and there is only one answer to that question? $\endgroup$
    – klm123
    Aug 13 at 1:50
  • $\begingroup$ @klm123 I think he means that he cannot tell you those things for the sake of this puzzle. $\endgroup$
    – Ankit
    Aug 13 at 2:10
1
$\begingroup$

A will always be

a knight

The reasoning for how we know this:

If A is normal, then we can get a yes or no for the first answer no matter what $S$ is. Because we don't know anything about A's identity after the first question, the answer we get for the $S$ we ask about must be something that either a knight or knave could have said under some circumstance. Thus, the answer to the second question must allow us to distinguish between one case where A is a knight, one case where B is a knave, and the two cases where A is normal.

For the (K)night, (N)ormal, and Knave (sometimes called a (J)oker), we get six possible arrangements and the following possible answers to the second question:

Arrangement | Q2 answer
K N J | K N J
K J N | K J
J N K | K N J
J K N | N
N J K | N J
N K J | J

From this we can see that if the answer to the second question is that C is a knave or normal, we won't be able to tell if A was a normal or not. So the answer to the second question must be that C is a knight. Either arrangement with A being a knight allows for that answer, so in order for "C is a knight" to distinguish between A being a knight or knave, we must have narrowed the possibilities down to one of the possibilities where A is a knight, the possibilities where A is normal, and the possibility where A is a knave and B is a knight. So "C is a knight" will always rule out A being normal and B being a knight, leaving A to be the knight.

Here's one possible solution for the questions and identities of the three:

$S$ is

the set of the two possibilities where B is normal. In other words, it is equivalent to asking "is B normal?"

When asked if $S$ contains the correct possibility

A said yes. This could mean A is normal, or that A is a knight and B is normal, or that A is a knave and B is the knight.

When asked about C, B said

C is a knight.

Using this, we can determine the identities of A, B, and C:

Neither the knight nor the knave would claim the other is a knight, so A is not normal. Based on the response to the first question we know B is either normal or the knight, but the knight would not claim anyone else was the knight so B must be normal. So A is the knight, B is normal, and C is the knave.

Here's another possibility:

$S$ is

the set {(Knight, Normal, Knave), (Knave, Knight, Normal)}.

When asked if $S$ contains the correct possibility:

A said no. This could mean A is normal, or that A is a knight and the first possibility in the set swaps the normal and knave, or that A is a knave and the second possibility in the set is correct.

When asked about C, B said

C is a knight.

Using this, we can determine the identities of A, B, and C:

Neither the knight nor the knave would claim the other is a knight, so A is not normal. A can't be a knave either, because then B would be a knight claiming a normal was a knight. So A is the knight, B is the knave, and C is the normal.

$\endgroup$
6
  • $\begingroup$ Is this the only possible solution, or are there more? $\endgroup$
    – bobble
    Aug 12 at 20:40
  • 1
    $\begingroup$ I don't think this works - it would be possible to deduce from A's answer that A is normal, which contradicts the statement in the problem that A's answer did not give the traveller enough information to rule out the possiblility that A is a knight. $\endgroup$
    – fblundun
    Aug 12 at 20:42
  • $\begingroup$ @fblundun found one that doesn't run into that issue. $\endgroup$
    – Rob Watts
    Aug 12 at 21:34
  • 1
    $\begingroup$ I think you can have a solution for any of the 4 S that pairs an A:knight state with an A:knave state. The answer to Q1 will leave you with one of the A:knight states, the A:knave, B:Knight state and the A:Normal states. The Q2 answer is always "C is a knight" with removes the A:knave and A:Normal states. $\endgroup$ Aug 12 at 22:07
  • $\begingroup$ @RobWatts you found a solution that I didn't expect! Thanks - I've edited the original question so that it only asks for A's type which I think makes it solvable. $\endgroup$
    – fblundun
    Aug 12 at 22:08
-1
$\begingroup$

Answer:

You don't know the inhabitants' identities.

Proof:

While the first question may have 2 possibilities and the second 3 possibilities, combining together into 6 total possibilities (once for each case), this information alone is not enough to uniquely determine which configuration the three inhabitants are in. Namely, this is due to the fact that the information is not uniformly true or false.

Let's pick an arbitrary $S$ and create a table listing all possible configuration and answers to each question. The abbreviations used are G,V and N for knights, knaves, and normals respectively:

Arrangement | Q1     | Q2
G,V,N | ? | G, V
G,N,V | ? | G,N,V
V,G,N | ? | N
V,N,G | ? | G,N,V
N,G,V | yes,no | V
N,V,G | yes,no | N,V

No matter which answer is given for Q2, there at least 3 possiblities for how the inhabitants are arranged. Therefore, the 1 bit of information given by the first question is not enough to uniquely distinguish all 6 possibilities given just the two questions provided.

$\endgroup$
4
  • 2
    $\begingroup$ We're not told that the two questions are sufficient to determine their identities in all cases, only that for the particular answers A and B gave it was enough information to determine them. $\endgroup$
    – Rob Watts
    Aug 12 at 21:08
  • $\begingroup$ Sure, but I don't think a unique solution is possible for any answer given by A and B. Even in the most generous case of B declaring C to be a knight, that still only narrows things down to three possible cases. The yes/no question of Q1 does not provide enough information to identify the three inhabitants, regardless of S or how you reason about it. $\endgroup$
    – hazilnut
    Aug 12 at 21:27
  • 1
    $\begingroup$ @hazilnut that isn't true - for example, if $S$ is the set of both possibilities where B is a knight, and A claims that $S$ contains the true answer, and B claims that C is a knight, the traveller would be able to deduce that A is a knave, B is normal, and C is a knight. (Though this can't really be what happened, since the traveller would have been able to deduce immediately after A's answer that A was not a knight.) $\endgroup$
    – fblundun
    Aug 12 at 21:36
  • 1
    $\begingroup$ Your mistake is that you assume the possibilities need to be partitioned evenly. The one bit of information allows you to determine which of two partitions contains the correct possibility, but if you can partition them such that one contains only one possibility you can get it with just the one bit. As an example, if I wanted you to guess one of {1,2,3,4}, you could ask if it's odd to partition them between {1,3} and {2,4} - never enough to know for sure which number is right. Or you could ask if it's 1 and partition them {1} and {2,3,4}, which will sometimes get you the number in 1 question. $\endgroup$
    – Rob Watts
    Aug 12 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.