You are a detective investigating a robbery, with five suspects having made the following statements:

- Paul says, “Neither Steve nor Ted was in on it.”
- Quinn says, “Ray wasn’t in on it, but Paul was.”
- Ray says, “If Ted was in on it, then so was Steve.”
- Steve says, “Paul wasn’t in on it, but Quinn was.”
- Ted says, “Quinn wasn’t in on it, but Paul was.”

You do not know which, nor even how many, of the five suspects were involved in the crime. However, you do know that every guilty suspect is lying, and every innocent suspect is telling the truth. Which suspect or suspects committed the crime?

I think puzzles similar to this one make good, fun homework problems in a discrete mathematics course introducing propositional logic. However, this particular puzzle is a bit more complex than the usual “Which one of three suspects is guilty?” type, not just because there are more suspects, but also because we don’t know *how many* suspects are guilty.

That added complexity is motivated by trying to transform this typically pencil-and-paper mathematical logic problem into a potentially nice computer science programming exercise: consider writing a program to *automate* solving this problem… or even better, writing a program to *generate new random instances* of problems like this one, while ensuring that the resulting puzzle has some reasonably “nice” properties. For example, the solution should be unique; but the puzzle should also be “interesting,” in that we should need *all* of the suspects’ statements to deduce who is guilty (that is, any proper subset of the statements should imply at least two distinct possible solutions).

### Like this:

Like Loading...

*Related*

After some thought, I worked out what I think is a neat representation for solving it: https://pastebin.com/c85uJkiE

Each person’s claim has two components, a “care” mask (like “don’t care” in a Karnaugh map) to track which people they’re making claims about. The other component is a bit array of “in” and “out” indicators. A candidate solution is just a bit array of “in” and “out,” and to check it we just test it against everyone’s bit array, masking out the don’t cares and inverting the guilty.

The third rule in your example is tricky since it has a dependency. To represent this, there’s still one “care” mask, but there are three possible bit arrays to check. If Ray is innocent, at least one of these should match (OR). If Ray is guilty, none of them should match (e.g. De Morgan’s law).

To generate a puzzle from here, I’d probably just do the dumb thing: generate random claim sets and use this solver to check for each of the constraints you listed.

Cool. That’s one of the key parts of this problem, I think, to *represent* the statements in such a way that it it relatively easy to solve *different* instances of the same type of problem with different statements. (The English form of the statements can be a non-trivial hurdle for students; as your solution shows, the “if-then” nature of Ray’s statement doesn’t have to be a “new” primitive, but can be expressed either as an “or” or a negated “and”.)