Question 6
A conference has $n\ge10$ participants. Assume that:
1. Each person knows at least $\left\lfloor\frac{n+2}{3}\right\rfloor$ other participants.
2. Any two people $A,B$ who do not know each other are connected indirectly: there are $k\ge1$ people $A_1,\ldots,A_k$ such that $A$ knows $A_1$, $A_i$ knows $A_{i+1}$ for $i=1,\ldots,k-1$, and $A_k$ knows $B$.
3. It is impossible to place all $n$ people in a row so that every adjacent pair know each other.
Prove that the participants can be split into two groups: the first can sit around a round table so that every adjacent pair know each other, and in the second no two people know each other. (The square brackets printed in the source denote the integer part.)
The supplied source has no question point values. Each problem uses 1 editorial point for import compatibility; this is not an official scoring scale.
1. Each person knows at least $\left\lfloor\frac{n+2}{3}\right\rfloor$ other participants.
2. Any two people $A,B$ who do not know each other are connected indirectly: there are $k\ge1$ people $A_1,\ldots,A_k$ such that $A$ knows $A_1$, $A_i$ knows $A_{i+1}$ for $i=1,\ldots,k-1$, and $A_k$ knows $B$.
3. It is impossible to place all $n$ people in a row so that every adjacent pair know each other.
Prove that the participants can be split into two groups: the first can sit around a round table so that every adjacent pair know each other, and in the second no two people know each other. (The square brackets printed in the source denote the integer part.)
The supplied source has no question point values. Each problem uses 1 editorial point for import compatibility; this is not an official scoring scale.