[ Logic and set theory $]

A traveler visited a village where every person either always tells the truth or always lies. The villagers stood in a circle, and each one told the traveler whether the person to their right was truthful or a liar. Based on these statements, the traveler was able to uniquely determine what fraction of the village's population consists of truthful people. Determine what this fraction is.

#
How will the answers change if the truth-tellers are replaced by liars, and the liars by truth-tellers?

## Solution

Let x be the fraction of truthful residents. Consider another circle where all liars become truthful and all truthful residents become liars; in this circle, the fraction of truthful residents is 1-x. In this circle, the traveler will hear the same thing, because the truthfulness of any resident has changed, but the truthfulness of the neighbor they are talking about has also changed. Since the traveler was able to determine the fraction of truthful residents based on the answers received, this fraction is the same in both circles. Therefore, it is equal to $1 / 2$.

## Problem