Algorithmic Problem Solving

The island of knights and knaves is a fictional island that is often used to test students’ ability to reason logically. The island has two types of natives, “knights” who always tell the truth, and “knaves” who always lie. Logic puzzles involve deducing facts about the island from statements made by its natives without knowing whether or not the statements are made by a knight or a knave.

The temptation is to solve such problems by case analysis – in a problem involving n natives, consider the 2ⁿ different cases obtained by assuming that the individual natives are knights or knaves. Case analysis is a clumsy way of tackling the problems. In contrast, these and similar logic puzzles are easy exercises in the use of calculational logic, which we introduce in this chapter.

The form of this chapter diverges from our usual practice of referring the reader to Part II of the book. This is because the techniques needed are unfamiliar but very necessary. The chapter gives a first introduction to calculational logic – enough to solve the knights-and-knaves puzzles – while Chapter 13 takes the subject further for more general use.

5.1 LOGIC PUZZLES

Here is a typical collection of knights-and-knaves puzzles.

1. It is rumoured that there is gold buried on the island. You ask one of the natives whether there is gold on the island. The native replies: “There is gold on this island is the same ...