5. A health camp was visited by 175 schoolchildren. Some of the children know each other, while others do not. It is known that any six schoolchildren can be accommodated in two three-person rooms so that all schoolchildren in the same room know each other. What is the minimum number of pairs of schoolchildren who could have come to the camp knowing each other?
Answer: 15050.

Solution. Suppose that some student (let's call him Vasya) is not acquainted with at least four students. We will select the following six children: Vasya, four students he is not acquainted with, and one more arbitrary student. It is impossible to seat them in two rooms, since out of this six, Vasya is acquainted with no more than one person. Therefore, each student has no more than three unknowns. Let's consider two cases.

1) Each student is not acquainted with no more than two children. Then any student has at least 172 acquaintances, and the total number of pairs of acquaintances is no less than $\frac{175 \cdot 172}{2}=15050$.
2) There exists a student who is not acquainted with three children. Let's denote such a student by $A$, and the unknown people by $B_{1}, B_{2}$, and $B_{3}$. We will select the following six children: $A, B_{1}, B_{2}, B_{3}$, and two more arbitrary students $C$ and $D$. Since they can be seated in two three-person rooms, $A$ must end up in a room with $C$ and $D$. But then students $C$ and $D$ must be acquainted with each other and with $A$. Thus, we have established that any students, other than $B_{1}, B_{2}$, and $B_{3}$, are acquainted with each other. In particular, this means that any student, other than $B_{1}, B_{2}$, and $B_{3}$, can be not acquainted only with someone from $B_{i}$. But each $B_{i}$ is not acquainted with no more than three students, so the number of pairs of unknowns does not exceed nine. Therefore, the number of pairs of acquaintances is no less than $\frac{175 \cdot 174}{2}-9=15216>15050$.
![](https://cdn.mathpix.com/cropped/2024_05_06_66368caef28b3de8e403g-20.jpg?height=290&width=910&top_left_y=2216&top_left_x=618)

Considering 1) and 2), it remains to show that the number of pairs of acquaintances can be exactly 15050. Let's seat all the students at a large round table and make everyone acquainted except those sitting next to each other. Let's check that this construction satisfies the problem's condition. Since each student is acquainted with 172 students, the total number of pairs of acquaintances is exactly $\frac{175 \cdot 172}{2}=15050$. Take any six students and seat them in two rooms. Remove all the others from the large round table and denote the remaining ones in a cyclic order as $A, B, C, D, E, F$. Now seat students $A, C, E$ in one room, and $B, D, F$ in the other. The inhabitants of each room are not sitting next to each other at the table, and, in particular, they were not sitting next to each other at the large table. Therefore, they all know each other.