Problem 12.3. In a group of $n$ people there are three that are familiar to each other and any of them is familiar with more then the half of the people in the group. Find the minimum possible triples of familiar people?

Nickolay Khadzhiivanov
12.3. Denote by $A, B$ and $C$ the three familiar people in the group.

Let $n=2 k+1$ be odd integer. Then any of $A, B$ and $C$ has at least $k+1$ familiar ( $k-1$ of them are not $A, B$ or $C$ ). Denote by $T$ the set of all people except $A, B$ and $C$ a let $a_{i}, i=0,1,2,3$, be the set of the people in $T$ who have exactly $i$ familiar among $A, B$ and $C$.

Then $a_{0}+a_{1}+a_{2}+a_{3}$ is the number of all members of $T$, i.e. we have

$$
a_{0}+a_{1}+a_{2}+a_{3}=2 k-2
$$

On the other hand, $a_{1}+2 a_{2}+3 a_{3}$ is the number of all familiar to $A, B$ and $C$, i.e. we have

$$
a_{1}+2 a_{2}+3 a_{3} \geq 3 k-3
$$

Hence

$$
\begin{aligned}
3 k-3 & \leq a_{1}+2 a_{2}+3 a_{3}=a_{0}+a_{1}+a_{2}+a_{3}+a_{2}+2 a_{3} \\
& =2 k-2+a_{2}+2 a_{3}
\end{aligned}
$$

and therefore $a_{2}+2 a_{3} \geq k-1$.

Since any familiar to two of $A, B$ and $C$ is a member of a triple of familiar people and any familiar to $A, B$ and $C$ is member of three such triples, then the number of these triples is at least $1+a_{2}+3 a_{3}$. Thus $1+a_{2}+3 a_{3}>a_{2}+2 a_{3} \geq$ $k-1$, which means that the number of the triples is not less than $k$.

It remains to construct an example with $k$ triples of familiar people. Let there are no familiar people in $T$. If $A$ is familiar to exactly $k-1$ people of $T$, and $B$ and $C$ - to the remaining $k-1$, then the number of the triples is $k$.

Let $n=2 k$ be even number. As in the previous case, we get that the number of the triples of familiar people is at least $k+1$. If $A$ and $B$ have exactly one common familiar person from $T$ (it is possible, since $|T|=2 k-3$ and the familiar to $A$ and $B$ are at least $k-1$ ) who is not familiar to $C$, then the number of the triples is exactly $k+1$.

So the answer of the problem is $k$ for $n=2 k+1$ and $k+1$ for $n=2 k$.

Remark. The problem can be solved applying of the inclusion-exclusion principle to the sets of persons which are familiar to $A, B$ and $C$, respectively.