A knight/knave/outcast logic puzzle from Smullyan's "Gödelian Puzzle Book"

Question

Here's a puzzle/riddle from a book I came across: does anyone know how to solve it?

According to the book the solution is Greg but I can't figure out how to get that answer - quite stuck on how to even get started.

From Raymond Smullyan, The Gödelian Puzzle Book: Puzzles, Paradoxes & Proofs:

A logician once visited a very strange island in which not every inhabitant was either a knight (who always told the truth) or knave (who always lied). Those who were neither one were called outcasts.

An outcast would lie on some days and be truthful on others. On any day, he would either lie the entire day, or be truthful the entire day, but his behavior could change from day to day.

On a given day, to say that a person is currently truthful is to say that he is either a knight (who is truthful on all days) or that he is an outcast and that day is one of his truthful days.

The logician was captured by a tribe of bandits. Curiously enough, the chief bandit was a knight, and this fact was common knowledge. He had been interested in logic and loved to test his victims.

And so he led the logician into a room with nine natives and explained that only one of them was a knight—each one of the other eight was either a knave or an outcast. The logician’s task was to determine which one was the knight. If he succeeded, he would be set free; otherwise, he would be executed. Here is what the nine men said.

Archie: The knight is either Cary, Elmak, Greg or myself.
Barab: I am an outcast.
Cary: Either Elmak is currently truthful or Greg is not.
Dreg: Archie lied.
Elmak: Barab and Dreg didn’t both lie.
Frisch: Cary lied.
Greg: Archie is not the knight.
Hal: I am a knave and Ilak is an outcast.
Ilak: I am a knave and Frisch lied.

The logician thought about this for while and finally said, "I don’t have enough information to solve the problem. I need to know whether or not Hal is an outcast. Then I might be able to solve it." The chief bandit was fair enough to tell him whether or not Hal was an outcast, and the logician could then figure out which one was the knight.

Which one was the knight?

Source: page 38 chapter 4 of the Puzzle Book

Answer 1

Let's go through some of the statements and see what we can figure out. (This ended up being a nearly complete solution, so try to read only one at a time to leave something for you to do!):

1. Observe that Hal is not a truth teller. If Hal were a truth teller, then Hal's statement "I am a knave" would be true, which is not possible since knaves are liars. Therefore, Hal is either a knave or an outcast (liar). There are two cases: A. Hal is a knave. In this case, Ilak must not be an outcast since otherwise Hal's statement would be true. B. Hal is an outcast (liar). In this case, we cannot conclude anything about Ilak from Hal's statement.

2. A similar statement holds for Ilak as for Hal. Therefore, if Hal is a knave, then Ilak is not an outcast. Since Ilak is either an outcast or a knave, Ilak must be a knave and Frisch must be telling the truth.

3. Barab is either an outcast (truth) or a knave. If Barab were a knight, then Barab's statement would be false and if Barab were an outcast (liar), then Barab's statement would be true.

4. Let's assume that Frisch is telling the truth. Then Cary is not telling the truth, so Elmak is a liar and Greg is truthful. Since Elmak is not telling the truth, both Barab and Dreg lied. Since Greg is truthful, Archie is not a knight. Since Barab lied, Barab is a knave. Since Dreg lied, Archie is telling the truth. Therefore, Archie is an outcast (truth). Therefore, one of Cary, Elmak, or Greg is a knight. Since we've seen that both Cary and Elmak are liars, it must be that Greg is the knight.

5. Therefore, if the logician is told that Hal is a knave, the logician can conclude that Frisch is telling the truth so Greg is a knight.

6. Suppose now that Frisch is a liar. Then Cary is telling the truth. Therefore, either Elmak is truthful or Greg is a liar. A. If Greg is truthful, then Elmak is truthful, then either Barab is truthful or Dreg is truthful. If Barab is a liar, then Dreg is truthful, so then Archie is a liar, so none of Cary, Elmak, Greg, or Archie can be the knight. Then Dreg is the knight. B. If Greg is truthful, then Elmak is truthful, then either Barab is truthful or Dreg is truthful. If Barab is telling the truth, then Barab is an outcast (truth). The possibilities for the knight are Cary, Dreg, Elmak, or Greg. C. If Greg is a liar, then Archie is the knight.

7. If the logician is told that Hal is an outcast, the logician cannot conclude that Ilak is either a knave or an outcast, so Frisch may or may not be a liar.

For each final case, you should write down a set of values for each of the people that are not self-contradictory to be sure that each case that we found is actually possible (i.e., that we didn't miss any logical connections).