Question 38
Let $k \ge 1$ be an integer. In a group of $2k+1$ people, some are sincere (they always tell the truth) and the rest are unpredictable (sometimes they tell the truth and sometimes they lie). It is known that the unpredictable ones are at most $k$. Someone outside the group must determine who is sincere and who is unpredictable through a sequence of steps. In each step he chooses two people $A$ and $B$ from the group and asks $A$ is $B$ sincere?
Show that after $3k$ steps the outsider will be able to classify $2k+1$ the people in the group with certainty.
Show that after $3k$ steps the outsider will be able to classify $2k+1$ the people in the group with certainty.