5. In the village of Beryozovka, there are 200 residents, some of whom are acquainted with each other, while others are not. It is known that any six residents can be seated at a round table such that each of them is acquainted with both of their neighbors. What is the minimum number of pairs of acquainted residents in Beryozovka?
Answer: 19600.

Solution. Suppose that some resident (let's call him Vasya) is not acquainted with at least four other residents. We will select the following six people: Vasya, four residents he is not acquainted with, and one more arbitrary person. They cannot be seated around a round table in the required manner, since there will inevitably be an unfamiliar person sitting next to Vasya. Therefore, each resident of the village cannot have more than three unfamiliar people. Hence, each is acquainted with at least 196 residents, and the number of pairs of acquaintances is no less than $\frac{200 \cdot 196}{2}=19600$.

![](https://cdn.mathpix.com/cropped/2024_05_06_66368caef28b3de8e403g-16.jpg?height=277&width=280&top_left_y=1575&top_left_x=951)

Now, let's show that the number of pairs of acquaintances can be exactly 19600. Seat all residents around a large round table. We will call two people almost opposite if there are at least 98 people sitting between them in both directions. Now, let's make all residents acquainted with each other except those sitting almost opposite. Since each resident is not acquainted with exactly three others, each is acquainted with exactly 196 people, and the total number of pairs of acquaintances is $\frac{200 \cdot 196}{2}=19600$. Now, take any six residents and denote them (in the order of their seating at the table) as $A_{1}, \ldots, A_{6}$. If in this cycle all neighbors are acquainted with each other, the desired seating arrangement is found. Otherwise, there exist two unfamiliar neighbors (let these be $A_{1}$ and $A_{2}$). Number all people at the large table in the same cyclic order from 1 to 200, starting with $A_{1}$. Note that the numbers of two unfamiliar residents can differ only by 99, 100, or 101. Let $N_{1}, \ldots, N_{6}$ be the numbers of $A_{1}, \ldots, A_{6}$, respectively. Then $N_{1}=1$ and $N_{2} \geqslant N_{1}+99=100$. Since the numbers $N_{i}$ are natural and strictly increasing, for $i \geqslant 2$ the inequalities $98+i \leqslant N_{i} \leqslant 194+i$ hold. Let's make two simple observations.

1) Resident $A_{1}$ is acquainted with $A_{5}$ and $A_{6}$. Indeed, for $i=5$ or $i=6$,

$$
N_{i}-N_{1}=N_{i}-1 \geqslant N_{5}-1 \geqslant 103-1=102>101
$$

2) For $2 \leqslant j < i \leqslant 6$, $A_{i}$ is acquainted with $A_{j}$. Indeed, $N_{i} > N_{j}$ and

$$
N_{i}-N_{j} \leqslant 194+i-(98+j)=96+(i-j) \leqslant 98<99
$$

Now, from 1) and 2) it follows that the cyclic seating arrangement $A_{1} \rightarrow A_{5} \rightarrow A_{3} \rightarrow A_{2} \rightarrow A_{4} \rightarrow A_{6} \rightarrow A_{1}$ satisfies the condition of the problem.