6. In an attempt to colonize Mars, humanity flooded the solar system with 50 satellites, which established 225 communication lines between them (each line exists between one pair of satellites, and no two satellites have more than one line between them). We say that a trio of satellites is connected if one of them has communication lines established with both of the other two satellites. Determine the smallest and largest possible number of connected trios of satellites. (The order of satellites in pairs or trios does not matter.)

(Ján Mazák, Josef Tkadlec)
SOLUTION. We will prove in two separate parts that satellites can form at least 600 and at most 5400 connected triples. Throughout the text, $S$ will denote the set of tangent satellites, $n=50$ their number, and $m=225$ the number of communication lines.

a) The maximum possible number of connected triples is 5400.

A triple of satellites is connected if and only if it contains two or three communication lines. It is therefore beneficial for each possible value $i \in \{0,1,2,3\}$ to denote as $t_{i}$ the number of those triples of satellites that have exactly $i$ communication lines. We claim that these numbers satisfy the equation

$$
\sum_{i=0}^{3} i \cdot t_{i}=m \cdot (n-2)
$$

Indeed, both sides express the total number of ordered pairs $(T, l)$, where $T$ is a triple of satellites and $l$ is a communication line between two satellites of this triple, because on the left side we count for each individual $T$ how many pairs $(T, l)$ a given $T$ appears in, while the right side (1) expresses the fact that each $l$ appears in $n-2$ pairs $(T, l)$.

From the proven equation (1) rewritten in the form $t_{1}+2 t_{2}+3 t_{3}=m(n-2)$, we get an estimate for the number $t_{2}+t_{3}$ of all connected triples of satellites:

$$
t_{2}+t_{3}=\frac{m(n-2)-t_{1}-t_{3}}{2} \leqq \frac{m(n-2)}{2}=5400
$$

the desired equality $t_{2}+t_{3}=5400$ holds if and only if $t_{1}=t_{3}=0$. This can be achieved if the satellites are connected as shown in the left image (where we indeed have $5+45=50$ satellites and $5 \cdot 45=225$ communication lines).

![](https://cdn.mathpix.com/cropped/2024_04_17_ac22d29c13467b278f95g-13.jpg?height=274&width=734&top_left_y=1982&top_left_x=313)

45 satellites

![](https://cdn.mathpix.com/cropped/2024_04_17_ac22d29c13467b278f95g-13.jpg?height=334&width=508&top_left_y=1915&top_left_x=1251)

$5 \cdot\left(\begin{array}{c}10 \\ 2\end{array}\right)=225$ lines

b) The minimum possible number of connected triples is 600.

For a connected triple of satellites $T$ and its satellite $s$, we say that $s$ is the central satellite of the triple $T$ if it is connected to both other satellites of this triple. Note that each connected triple has either one or three central satellites.

Define the degree $d_{s}$ of a satellite $s$ as the number of communication lines it has. Then $s$ is the central satellite in exactly $\left(\begin{array}{c}d_{s} \\ 2\end{array}\right)=\frac{1}{2} d_{s}(d_{s}-1)$ connected triples. Since each connected triple has at most 3 central satellites, for the total number $P$ of connected triples, we have

$$
P \geqq \frac{1}{3} \sum_{s \in S}\left(\begin{array}{c}
d_{s} \\
2
\end{array}\right)=\frac{1}{6}\left(\sum_{s \in S} d_{s}^{2}-\sum_{s \in S} d_{s}\right) \geqq \frac{1}{6}\left(\frac{1}{n}\left(\sum_{s \in S} d_{s}\right)^{2}-\sum_{s \in S} d_{s}\right),
$$

where the last inequality follows from the inequality between the quadratic and arithmetic mean for the $n$-tuple of numbers $\left(d_{s} \mid s \in S\right)$, which is itself a consequence of the Cauchy-Schwarz inequality

$$
\left(\sum_{s \in S} 1 \cdot d_{s}\right)^{2} \leqq\left(\sum_{s \in S} 1^{2}\right) \cdot\left(\sum_{s \in S} d_{s}^{2}\right)
$$

The sum $\sum_{s \in S} d_{s}$, which appears in the derived estimate, is equal to twice the number $m$ of all communication lines, because each line is counted exactly twice in it (once for each of its ends). By substituting the value $2 m=450$ for $\sum_{s \in S} d_{s}$ along with the value $n=50$ into the derived inequality, we get the promised estimate

$$
P \geqq \frac{1}{6}\left(\frac{1}{50} \cdot 450^{2}-450\right)=600 \text {. }
$$

Furthermore, from our procedure, it follows that the equality $P=600$ holds if and only if all $P$ connected triples have three central satellites each and all $n=50$ satellites have the same degree, which is therefore known to be $2 m / n=9$. This can be achieved if the satellites are connected as shown in the right image (all 50 satellites are divided into five communicationally isolated groups of ten mutually connected satellites, each having the same degree of 9).

## NOTES.