In a certain country, there are 21 cities and the government plans to build $n$ roads (all two-way), each connecting exactly 2 of the country's cities. What is the smallest value of $n$ such that, regardless of how the roads are built, it is possible to travel between any 2 cities (possibly passing through intermediate cities)?
Solution

We will say that a group of cities is connected if it is possible to travel from one of them to any other by means of roads. Naturally, distinct connected groups of cities cannot have cities in common. If the government builds all the roads of a group of 20 cities and leaves one city isolated without roads, the property that all cities belong to the same connected group will not be established. Therefore, $n>\binom{20}{2}=190$. We will now show that if the government builds 191 roads, all cities will be part of the same connected group. Indeed, suppose there is more than one connected group and let $k$, with $1 \leq k \leq 20$ be the number of vertices of one of them, which we will call $A$. We recall that if we connect all the possible roads in a group of $n$ cities, we will obtain $\frac{n(n-1)}{2}$ roads. Since there must not be any roads between group $A$ and the other groups that contain the remaining $21-k$ cities, the total number of roads is not greater than

$$
\begin{aligned}
\frac{k(k-1)}{2}+\frac{(21-k)(20-k)}{2} & = \\
k^{2}-21 k+210 & = \\
(k-21 / 2)^{2}+399 / 4 & \leq \\
(19 / 2)^{2}+399 / 4 & =190
\end{aligned}
$$

This is an absurdity, since the government built 191 roads. Thus, the smallest value of $n$ is 191.