12 A space station consists of 25 chambers, and each two chambers are connected by a tunnel. There are a total of 50 main tunnels that can be used in both directions, the rest are all one-way tunnels. A group of four chambers is called connected if you can get from any of these chambers to any other by using only the six tunnels that connect these chambers to each other. Determine the largest possible number of connected groups of four.

## Solution
If there is a chamber in a group of four from which three one-way tunnels lead away, this group is certainly not connected. We call such a chamber isolated in the group. Number the chambers and assume that $a_{k}$ one-way tunnels lead away from the $k$th chamber. In total, there are $\binom{25}{2}-50=250$ one-way tunnels. Therefore, $a_{1}+\ldots+a_{25}=250$, because each one-way tunnel leads out of exactly one chamber. The $k$-th chamber is isolated in exactly $\binom{a_{k}}{3}$ groups of four, so there are at least

$$
X=\binom{a_{1}}{3}+\binom{a_{2}}{3}+\ldots+\binom{a_{25}}{3}
$$

unconnected groups of four. We now claim that $X$ assumes the smallest possible value if all $a_{k}$ are the same size. If $r-2 \geq s \geq 0$ applies, then a quick calculation shows that

$$
\binom{r}{3}+\binom{s}{3}>\binom{r-1}{3}+\binom{s+1}{3} \Longleftrightarrow(r-1)(r-2)>s(s-1)
$$

and the latter is true by assumption. So if $X$ assumes its minimum, then two of the $a_{k}$ may not differ by more than 1. However, since their sum 250 is divisible by 25, they must all be the same size, as claimed. The following therefore applies $X \geq 25 \cdot\binom{10}{3}=3000$. Consequently, there are at most $\binom{25}{4}-3000=9650$ connected groups of four.

We now show that this value can also be achieved. To do this, we construct an arrangement of the tunnels as follows: Arrange the chambers on a circle and number them $K_{1}, \ldots, K_{25}$ clockwise. In the following, consider all indices modulo $25 \mathrm{to}$. From the chamber $K_{n}$ one-way tunnels lead to the chambers $K_{n+1}, \ldots, K_{n+10}$, the chambers $K_{n+11}, \ldots, K_{n+14}$ are connected to $K_{n}$ by a main tunnel, and finally one-way tunnels lead from the chambers $K_{n+15}, \ldots K_{n+24}$ to $K_{n}$. It is easy to see that this results in a well-defined configuration.

According to the construction and what has already been shown, this configuration contains exactly 3000 groups of four with an isolated chamber. It is therefore sufficient to show that all groups of four are connected without an isolated chamber. Assume oBdA that $\left\{K_{1}, K_{r}, K_{s}, K_{t}\right\}$ with $1<r<s<t \leq 25$ is a group of four without an isolated chamber. We claim that the distances $r-1, s-r, t-s$ and $26-t$ (i.e. the distances between consecutive chambers in clockwise direction) are all smaller than 15. If two consecutive chambers have a greater distance, then the second of the two is isolated by construction. Again by construction, the chambers can therefore be arranged in the order $K_{1} \rightarrow K_{r} \rightarrow K_{s} \rightarrow K_{t} \rightarrow K_{1}$, so the group of four is indeed connected. This shows everything.