When some people are truthful and others lie, a single answer can mislead you. But if you know how to pair answers, lies can cancel out truths.
The Majority Adviser
Riddle statement
A king has 101 advisers. Each adviser is one of two types:
- truthful: always tells the truth;
- liar: always lies.
The king may choose two advisers, A and B, and ask A: “Is B truthful?”
How can he find, with certainty, an adviser who belongs to the majority type?
Show solution
Solution
The question gives a reliable comparison.
If A answers “yes,” then A and B are of the same type. If A is truthful, then B is truthful; if A is a liar, then the statement “B is truthful” is false, so B is also a liar.
If A answers “no,” then they are of different types.
With this comparison, the king applies majority cancellation. He keeps a candidate and a counter:
- Start with the first adviser as the candidate and set the counter to 1.
- Compare each new adviser with the current candidate.
- If they are of the same type, add 1 to the counter.
- If they are of different types, subtract 1.
- If the counter reaches 0, take the next adviser as the new candidate and reset the counter to 1.
Each subtraction cancels a pair made of one adviser of each type. Since there are 101 advisers, one type occurs more often than the other. After all opposite pairs have been canceled, the final candidate must belong to the majority type.
The king does not need to know whether that type is truthful or lying in order to achieve the goal.
Answer: use the answers as equality comparisons and apply the majority-cancellation algorithm.