Knights and liars around a table
Statement
Ten people sit around a round table. Each is either a knight (always tells the truth) or a liar (always lies). Each of them says: "Both my neighbours are liars." Find all possible numbers of knights.
Hint
What does the statement of a knight force on his neighbours? What does the lie of a liar force?
Show solutionHide solution
Solution
Constraints.
- A knight tells the truth, so both his neighbours are liars: no two knights are adjacent.
- A liar's statement is false, so at least one of his neighbours is a knight: no three consecutive liars.
Conversely, these two conditions are sufficient for consistency.
Counting. There is at least one knight. Let there be knights. Going around the circle, the knights split the remaining people into groups of consecutive liars. Each group has liar or liars (not : knights are not adjacent; not or more: no three consecutive liars). Hence
Both values occur.
- : alternate knight, liar, knight, liar, ...
- : groups of liars of sizes between the four knights ().
Answer. or knights.
Check. A computer search over all assignments finds exactly the solutions with or knights.
Lesson. Turn each statement into a local constraint, then count blocks between the special elements.