Whodunit logic puzzle

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).

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Whodunit logic puzzle

  1. 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”.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s