Knight, knave, commoner

[Communicated to me 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?

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

[Another variation of the problem.]

Find a strategy for the king where the king can ask questions of only one suitor, but can ask two questions of that suitor.

[And another (at first sight incredible) follow-up question communicated to me by both Jim Saxe and Pierre Nallet.]

Find a strategy for the king where the king can ask only one yes/no question and only of one suitor.

©2019 K.R.M. Leino - Split Template by One Page Love