# 12.3 Knights and Knaves

It's been many chapters since the detective story got paused. Last we saw you, you were on your way home after saving Quinn.

As soon as you reach home, you fall straight onto your bed. But instead of falling into sleep you just keep falling. The room starts spinning and the world becomes a blur.

The next thing you know you are lying on a beach. The soft sound of waves is punctuated by Whack! Whack! Whack!

You sit up and see three people pounding a signpost into the ground.

The sign says:

**The Island of Knights and Knaves**

1. Every resident is a knight or a knave.

2. Only residents are knights or knaves.

3. Knights always speak the truth.

4. Knaves always lie.

"Where am I?" you ask them.

"Can't you read?" the first person replies. Apparently this island has a problem with sarcasm as well as liars, you think to yourself.

You try again: "I mean, where is this island? How did I get here?"

"It's in the middle of the Pacific," the second person says.

"Don't listen to him," says the third. She shrugs. "He's nice but he's lying. He has to; he's a knave."

"No I'm not, I'm a knight!" the second one says.

"A knave *would* say that," says the first one, rolling his eyes.

"But so would a knight," you point out.

"Ooo," the second one smiles triumphantly.

"*Who are you, so wise in the ways of logic?*" the first one says in a sarcastic tone.

"I'm Detective K, and I'm just trying to get back home."

"It's nice to meet you, K," says the third. She gestures at the first person and then the second. "That's Ray. This is Smully. And I'm Anne. As to your question, I have no idea where in the world we are. I'm not from here either."

You look around bleakly.

"But how can I trust any of you? What if you *do* know where we are, but you're not Anne, and he's Smully and he's Ray?"

"You'll just have to figure out who to trust," says Ray.

"No," she replies.

"Progress!" you say. "Now I know you're not from here, since a knight and a knave would both say yes. Only a visitor could say no. Now can you tell me, how do I get off this island?"

"I have no idea," says Anne. "I've been stuck here for a year! If you can figure out who to trust around here, then maybe we've got a chance. I do know that they're both residents though. Just look at those t-shirts."

You finally notice that Ray and Smully are wearing the same shirt, which says "Kn*" on the front.

Now you need a plan. In the distance you can see two houses. One is on a hilltop overlooking the beach, and the other is in a valley, at the mouth of a dark woods.

"Which house can we go to for help?" you ask Ray and Smully.

"Go to the house on the hill," says Ray.

"Go to the house in the valley," says Smully.

"See," says Anne.

Hmm, you go into a deep think. Then you ask: "Are you both lying?"

Ray: "Yes, we are both lying."

Smully: "No, we're not both lying."

The trick to solving Knights and Knaves problems is proof by cases. We are assuming that Anne is right that Ray and Smully are both from the island. That means each is a knight or a knave. For all we know, they might both be knights, both be knaves, or one is a knight and the other a knave.

But at least we know these disjunctions: Ray is a knight or knave, and Smully is a knight or knave.

That means we can do proof by cases to try to discover something useful.

Let's start with Ray. He said "yes" to the question, so he is saying: we are both lying. Now take case 1: assume temporarily that Ray is a knight. Then it would have to be true that they are both lying. But a knight can't lie. So this case is contradictory; it is impossible. A knight could never say that. So Ray must be a knave.

In order for the puzzle to work properly, case 2 ought to be consistent. If case 2 is also contradictory, then there's a flaw with the puzzle: the assumptions of the puzzle contradict themselves.

Let's make sure that's not happening. Case 2 says that Ray is a knave. So it follows that it is false that they are both lying. A false conjunction means that one or both of them are telling the truth. But Ray is not telling the truth, since we are assuming in this case that he is a knave. So it follows that Smully is a knight. As long as that is possible, then the puzzle doesn't contradict itself.

In fact, it is possible that Smully is knight. Smully said that they are not both lying. If Smully is a knight, then it is true that they are not both lying, since he is not lying. So there is no contradiction here. We can know Ray is a knave and Smully is a knight.

All knights and knaves puzzles can be solved with disjunctive reasoning, though sometimes it takes a lot of work to figure them out.

You and Anne finally reach the house in the valley. A small stream runs through the backyard and disappears into the dark woods.

On the front door are two notes.

Anne says, "One of these notes was written by a knight, but I don't know which."

The first one says: "This note was written by a knight. To get off the island, you must enter the house and find the hidden door under a rug. And by the way, the other note was written by a knave."

The second note says: "Either I'm a visitor, or the person who wrote the other note is a resident. To get off the island, you must enter the dark woods."

Here's how we can prove that was the correct decision.

The author of the first note is a knight or a knave or maybe even a visitor. Take case 1: assume they are a knight. The last thing they said was that author #2 is a knave. Since we are assuming author #1 is a knight, it follows that #2 is a speaking falsely. But #2 said "I'm a visitor, or the author of the other note is a resident." That disjunction must be false.

In order for a disjunction to be false, both disjuncts must be false. The first disjunct is "I'm a visitor". That is indeed false, since #2 is a knave, and all knights and knaves are residents. The second disjunct is "the author of the other note is a resident." If that is false, that means author #1 is a visitor. But our working assumption is that they are a knight and hence a resident.

That means this case is impossible. If author #1 is a knight, then a contradiction follows. So author #1 can't be a knight.

We don't even have to consider the other cases now, because Anne said that one of them is a knight. Since it isn't #1, it must be #2. So #2 is speaking truly, and they said to go into the woods.

You and Anne start off into the woods. To be continued...