MathDB

Let

k\geq 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

B

sincere? Show that after

3k

steps the stranger will be able to classify with certainty the

2k+1

people in the group. (Before asking each question, the answers to the previous questions are known.)
Clarification: Each of the

2k+1

people in the group knows which ones are sincere and which ones are unpredictable.

Problem Statement