5. In the country of Alphia, there are 150 cities, some of which are connected by express trains that do not stop at intermediate stations. It is known that any four cities can be divided into two pairs such that there is an express train running between the cities of each pair. What is the minimum number of pairs of cities connected by express trains?
Answer: 11025.

Solution. Suppose that some city (let's call it Alfsk) is connected by express trains to no more than 146 cities. Then a quartet of cities, consisting of Alfsk and any three with which it is not connected, does not satisfy the problem's condition, since Alfsk cannot be paired with any of the three remaining cities. Therefore, each city is connected to at least 147 cities. Consequently, the total number of pairs of cities connected by express trains is no less than $\frac{147 \cdot 150}{2}=11025$.

Now, let's show that there can be exactly 11025 pairs of cities. Number the cities from 1 to 150 and connect by express trains all cities except the first and the 150th, as well as cities whose numbers differ by one. Let's check that this construction satisfies the problem's condition. Since each city is connected by express trains to 147 cities, the total number of connected city pairs is exactly $\frac{147 \cdot 150}{2}=11025$. Now, take any quartet of cities. There are two cases.

1) There is a city not connected to two of the three remaining cities. Let city $A$ not be connected to cities $B$ and $C$, but be connected to city $D$. Then cities $B$ and $C$ must be connected to each other, since the remainders of their numbers when divided by 150 differ by 2. Therefore, the pairs $(A, D)$ and $(B, C)$ are suitable.
2) All cities are connected to at least two of the three remaining cities. Let city $A$ be connected to cities $B$ and $C$. By assumption, city $D$ must be connected to $B$ or $C$. If it is connected to $B$, then the pairs $(A, C)$ and $(B, D)$ are suitable, and if to $C$, then the pairs $(A, B)$ and $(C, D)$.