Lying knaves

You don’t always need a big laboratory for exciting experiments... All you need to solve problems involving knights, knaves and muddy children is a good set of brains.

On a rainy island, surrounded by savage seas, lives a population made up of two types of inhabitants: knights and knaves. There is something peculiar about them: the noble knights always speak the truth, while the knaves always lie. One fateful day you make the awful mistake of booking a holiday to this rainy island, and now you have a problem: who is a knight and who is a knave?

During an evening walk you meet two of the island’s inhabitants, Frank and Ronald. You politely ask them if they happen to be knights or knaves. ‘We’re both knaves,’ answers Ronald.

Luckily, you’ve been on the island long enough to know for sure now that Ronald is a knave and Frank a knight. How? If Ronald had been a knight, his statement would have to have been true, which is a contradiction, as it would mean that Ronald was both a knight and a knave. Ronald is thus a knave, but this means that his statement was untrue. So, Frank is a knight.

‘The above problem is known as the knights and knaves puzzle,’ explains artificial intelligence student Maarten Jacobs. Last year he gave a workshop for pre-university secondary school students about this dilemma. ‘It’s a typical example of a problem that you can tackle with simple Boolean logic. To put it simply: if-then, yes, no and or,’ he explains. You can increase the puzzles infinitely. Let’s say that during your next walk you meet not two but nine islanders: Andrew, Helen, Rose, Maria, Rachel, Peter, Alice, Edward and Laurence. Andrew says that only a knave would say that Alice is a knave. Helen claims that Rachel is a knave and Rose says that Andrew and Laurence are both knaves.

As you produce a notebook, on which you furiously begin to scribble, Maria says: ‘I am a knight and Alice is a knave.’ For her part, Rachel claims that she and Maria are both knights, and Peter says that at least one of the following statements is correct: Alice is a knight or Rose is a knight.

Meanwhile, Alice is shaking her head: ‘It’s definitely not true that Maria is a knave.’ Edward says it’s not true that Rose is a knave and, last but not least, Laurence has his say: Either Maria or Peter is a knave. And so there you are...

Happily, you can simplify the problem by exchanging all the names and statements for mathematical notations. If you really want to have a go, the English Wikipedia page on knights and knaves describes the notations exactly. Should you succeed in finding the solution using the logical formulas, e-mail it to r.m.de.jonge[at]rug.nl. We tried but were unsuccessful.

Jacobs adds that solving puzzles like these is not that different from doing sudokus. One possible solution for a sub-question, whether it be a numeral in a box or the conclusion that either Alice or Maria is a knave, can determine a chain of subsequent possibilities.

On the internet you can find numerous logical puzzles. Another popular version is the riddle of the muddy children: n children are playing in a sandpit, whereby k children get mud on their foreheads. They can all see which children have mud on their faces, but they cannot see their own foreheads. A tactful parent passes by, who warns them: ‘At least one of you has mud on your forehead.’ Can the children discover if they have mud on their faces through logical reasoning?

Author: Ernst Arbouw