MathDB
Problems
Contests
National and Regional Contests
Argentina Contests
Argentina National Olympiad
2005 Argentina National Olympiad
6
6
Part of
2005 Argentina National Olympiad
Problems
(1)
sincere in 2k+1 people
Source: Argentina 2005 OMA L3 p6
5/12/2024
Let
k
≥
1
k\geq 1
k
≥
1
be an integer. In a group of
2
k
+
1
2k+1
2
k
+
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
k
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
A
A
and
B
B
B
from the group and asks
A
A
A
is
B
B
B
sincere? Show that after
3
k
3k
3
k
steps the stranger will be able to classify with certainty the
2
k
+
1
2k+1
2
k
+
1
people in the group. (Before asking each question, the answers to the previous questions are known.)Clarification: Each of the
2
k
+
1
2k+1
2
k
+
1
people in the group knows which ones are sincere and which ones are unpredictable.
combinatorics