3. (3 points) In a certain country, there are 100 cities. The Ministry of Aviation requires that every two cities be connected by a two-way flight operated by exactly one airline, and that it should be possible to travel from any city to any other city using the flights of each airline (possibly with layovers). What is the maximum number of airlines for which this is possible?

Answer: 50
Solution: Evaluation: in order to connect all cities, the airline must have at least 99 flights. In total, there are $100 \cdot 99 / 2$ pairs of cities, which means there are no more than 50 airlines.

Example: let's denote the cities as $a_{1}, a_{2}, \ldots a_{50}, b_{1}, b_{2}, \ldots, b_{50}$ in some way. Then the airline with number $k$ will connect

1) cities $a_{k}$ and $b_{k}$;
2) $a_{k}$ and each city $a_{i}$, where $i < k$
3) $a_{k}$ and each city $b_{i}$, where $i > k$
4) $b_{k}$ and each city $a_{i}$, where $i > k$
5) $b_{k}$ and each city $b_{i}$, where $i < k$.

Thus, cities $a_{i}$ and $a_{j}$ are connected by a flight of the airline with number $\max \left(a_{i}, a_{j}\right)$, cities $b_{i}$ and $b_{j}$ by the airline with number $\max \left(b_{i}, b_{j}\right)$, and cities $a_{i}$ and $b_{j}$ by the airline with number $\min \left(b_{i}, b_{j}\right)$.