$\textbf{Lying Politicians}$
Suppose $125$ politicians sit around a conference table. Each politician either always tells the truth or always lies. (Statements of a liar are never completely true, but can be partially true.) Each politician now claims that the two people beside him or her are both liars. What are the maximum possible number and minimum possible number of liars?
$\textbf{Answer}$
There will be at most $83$ and at least $63$ liars.
$\textbf{Analysis}$
The first thing is to determine what we can be certain about. It turns out that the following two conclusions can be derived from the given information:
- No two truth tellers can sit next to each other
- No three liars can sit in a row
Both conclusions are obvious. For a truth teller, the statement "both people besides me are liars" is true. This leads to the first conclusion above. For a liar, the statement is false, therefore at least one of them is a truth teller. Hence, the second conclusion above holds too.
Combining these two conclusions, we can assert that there can be either one or two liars sitting between two truth tellers. As such, there are at least half and at most two thirds of the attendants are liars. Given the total number is $125$ and these people are sitting in a circular manner, it is possible to have exactly one liar sitting in every pair of two neighboring truth tellers. This leads to $63$ liars. On the other hand, it is impossible to put two liars between all the pairs of two neighboring truth tellers. There will be at least one pair of truth tellers separated by just one liar. In this case, a total of $83$ liars can be accommodated.