$n$ people sit in a circle. Each of them is either a liar (always lies) or a truthteller (always tells the truth). Every person knows exactly who speaks the truth and who lies. In their turn, each person says 'the person two seats to my left is a truthteller'. It is known that there's at least one liar and at least one truthteller in the circle. Is it possible that $n=2017?$ Is it possible that $n=5778?$
Problem
Source: Israel National Olympiad 2018 Q1
Tags: logic, combinatorics
NikoIsLife
13.09.2019 08:18
The answer is $\fbox{No}$.
We know that for any person, the person is telling the truth if and only if the person two seats to his\her left is a truthteller. This is equivalent to saying that any pair of people who are one person apart are either both truthtellers or both liars.
Without loss of generality, let the names of the people be $P_1$, $P_2$, $P_3$,... $P_{2017}$. Let $a_i$ be $1$ if $P_i$ is a truthteller, and $0$ if a liar.
We have $a_i=a_{i+2}$ for all $i\in\{1,2,3,\ldots,2017\}$, where all indices are taken modulo $2017$.
Hence,
$$a_1=a_3=a_5=\cdots=a_{2015}=a_{2017}=a_2=a_4=\cdots=a_{2016}$$which means that the people are either all truthtellers, or all liars, which is a contradiction.
The answer is $\fbox{Yes.}$
Let the people be $P_1$, $P_2$, $P_3$, ..., $P_{5778}$. Consider when all odd numbered people are truthtellers, and all even numbered people are liars.