Challenge Problem: Brain Teasers
submitted by Jeannette Wing, with thanks to Rustan Leino, Carroll Morgan, and Lyle Ramshaw

Knights, Knaves, and Commoners

These mathematical puzzles have nothing to do with software security, but I find them lots of fun!

1. Original: communicated to Rustan Leino by Carroll Morgan:

A king has a daughter and wants to choose the man she will marry.  There are three suitors from whom to choose: a Knight, a Knave, and a Commoner.  The king wants to avoid choosing the Commoner as the bridegroom, but he does not know which man is which.  All the king knows is that the Knight always speaks the truth, the Knave always lies, and the Commoner can do either.  The king will ask each man one yes/no question, and will then choose who gets to marry the princess.  What question should the king ask and how should he choose the bridegroom?

2. For the advanced student:  Here is a follow-up question posed by Lyle Ramshaw:

Suppose the three suitors know each other (an assumption that's not needed in the original problem).  Then find a new strategy for the king where the king only needs to ask a question of any two of the three suitors in order to pick the bridegroom.

Solutions