11.9. In the company, there are 100 children, some of whom are friends (friendship is always mutual). It is known that by selecting any child, the remaining 99 children can be divided into 33 groups of three such that in each group, all three are pairwise friends. Find the minimum possible number of pairs of friends.

(S. Berlov, N. Vlasova)
Answer: 198.

Solution: Let's translate the problem into the language of graphs, associating each child with a vertex and each friendship with an edge. Then we know that in this graph with 100 vertices, after removing any vertex, the remaining vertices can be divided into 33 triples such that the vertices in each triple are pairwise connected. We need to find the minimum possible number of edges in such a graph.

First, let's construct an example with exactly 198 edges. Divide 99 vertices, except for vertex $A$, into 33 groups of 3 vertices each. Connect the vertices pairwise within each triple; finally, connect $A$ to all other vertices. Then the conditions of the problem are satisfied: if $A$ is removed, the division into triples is already given, and if any other vertex $B$ is removed, in this division, it is sufficient to replace $B$ with $A$. In this described graph, there are a total of $33 \cdot 3 + 99 = 198$ edges.

It remains to prove that this number is the smallest.
We will call a graph on $3k+1$ vertices good if, after removing any vertex, the remaining $3k$ vertices can be divided into $k$ triples that are pairwise connected. We will prove by induction on $k$ that in a good graph on $3k+1$ vertices, there are at least $6k$ edges; for $k=33$, we will get the required estimate. The base case for $k=1$ is simple: since after removing any vertex, the remaining three are pairwise connected, any two vertices must be connected, so the number of edges is $C_{4}^{2}=6$.

Let's prove the inductive step. If from each vertex at least 4 edges come out, the total number of edges is not less than $(3k+1) \cdot 4 / 2 = 2(3k+1)$, which is even more than the required $6k$. Otherwise, there is a vertex $A$ connected to no more than three other vertices. If any vertex other than $A$ is removed, $A$ will end up in some triple, which means it is connected to at least two vertices. If one of these vertices is removed, $A$ will still have at least two adjacent vertices, so there were at least three. Thus, $A$ is connected to exactly three vertices $B, C$, and $D$. Then, when, for example, $B$ is removed, the vertices $A, C$, and $D$ form a triple, so $C$ and $D$ are connected; similarly, we get that $B$, $C$, and $D$ are pairwise connected.

Now, let's remove from our graph the vertices $A, B, C$, and $D$, and add one vertex $X$ connected to all those with whom at least one of the vertices $B, C$, and $D$ was connected. Note that in this case, the number of edges decreases by at least 6 (i.e., by the number of edges between $A, B, C$, and $D$). We will show that the resulting new graph is good; from this, the inductive step will follow, and then in the new graph, there will be at least $6(k-1)$ edges, which means in the original graph, there are at least $6(k-1) + 6 = 6k$ edges.

Suppose some vertex $Y \neq X$ is removed from the new graph. If it is removed from the original graph, the remaining vertices will be divided into triples; let's say, for definiteness, that vertex $A$ ends up in a triple with $B$ and $C$, and vertex $D$ in another triple. Then the new graph can be divided in the same way, placing vertex $X$ in the triple where vertex $D$ was. Finally, if vertex $X$ is removed from the new graph, the same operation can be performed, considering that vertex $D$ is removed from the original graph (then $A, B$, and $C$ will automatically end up in one triple). Thus, the inductive step is proven.

Remark. The provided example is not the only one. The reasoning in the second part of the solution essentially shows that many different optimal examples can be constructed in the following inductive manner. For $k=1$, take 4 vertices and connect all pairs with edges. When transitioning from $k$ to $k+1$, add three vertices $B, C, D$, connect them pairwise with each other, and also connect them all to some already existing vertex $A$.

In such an example, there will always be $6k$ edges, and it will satisfy the conditions of the problem.

Comment. Only the correct answer - 0 points.

Only an example with 198 pairs of friends is provided - 1 point.

Examples with more pairs of friends are not evaluated.

Only the proof that the number of pairs of friends is not less than $198-6$ points.