Problem #43 MEDIUM
The Liars at the Round Table
Microsoft Apple Game Theory Constraints
Problem Statement
Ten people are seated around a circular table. Each person is either a truth-teller (always honest) or a liar (always dishonest). Every single person at the table says: 'Both of my neighbours are liars.' Given this, how many truth-tellers are seated at the table, and how are they arranged?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Exactly 5 truth-tellers and 5 liars, seated in a strictly alternating pattern around the table. Truth-tellers have two liar neighbours (statement true). Liars have two truth-teller neighbours (statement false). This is the only valid configuration.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Analyse the statement's implications for both truth-tellers and liars, then check which consistent global configurations exist around a 10-person circular table.
Step 1: Suppose person X is a truth-teller. Their statement 'both neighbours are liars' is true. So both neighbours of X must be liars.
Step 2: Now look at a liar neighbour of X. They say 'both my neighbours are liars' — but this is false (since X is a truth-teller next to them). So at least one of the liar's neighbours is a truth-teller. That is already satisfied by X being adjacent.
Step 3: The constraint from truth-tellers: no two truth-tellers can be adjacent (each needs liar neighbours on both sides).
Step 4: With 10 seats in a circle, if truth-tellers cannot be adjacent, maximum truth-tellers = 5 (every other seat).
Step 5: Test alternating T-L-T-L-T-L-T-L-T-L around a 10-seat circle: each truth-teller has two liar neighbours (statement true — good). Each liar has two truth-teller neighbours. Liar's statement: 'both neighbours are liars' — this is false (both are truth-tellers). A liar saying something false is consistent.
Step 6: So the alternating arrangement works: exactly 5 truth-tellers and 5 liars, seated alternately.
Key Insight:
The key is testing whether a proposed arrangement is internally consistent — do truth-tellers have liar neighbours (validating their true statement) and do liars have at least one non-liar neighbour (making their statement false)? The alternating T-L pattern is the unique solution for a 10-seat circle.