Problem 8. (5 points)

In a certain country, there are 100 cities. Each of them is connected by two-way air routes to three other cities. Moreover, from any city, it is possible to reach any other city, possibly with transfers. Vasya wants to get from city A to city B. What is the smallest number of flights that are guaranteed to be sufficient for him?

#
# Answer: 72

Solution:
![](https://cdn.mathpix.com/cropped/2024_05_06_1522dcaa40cd2ee0cc58g-4.jpg?height=276&width=1888&top_left_y=204&top_left_x=107)

Before us is a scheme of air routes in a country, where it would take more than 71 flights to travel from city 1 to city 100. The main part of the scheme consists of repeating blocks of 4 cities, see cities $5, 6, 7$ and 8.

To get from city 1 to city 5, it takes 2 flights, then from city 5 to city 93, it takes 3 flights for every 4 cities, which is 66 flights, and another 4 flights to travel from city 93 to city 100, totaling a minimum of 72.

On the other hand, 72 flights are always sufficient to travel from any city to any other.

To prove this, place any starting city at level 0, the cities connected to it (which we will call neighboring) at level 1, their remaining neighbors at level 2, and so on. Each time, we place cities at level $k+1$ that are neighbors of cities at level $k$, if they have not been assigned another level before. (The example above is drawn according to this principle).

Each city at level $k$ can only be connected to cities at levels $k-1, k$, and $k+1$. This means that in any three consecutive levels, there are at least 4 cities in total. Additionally, there are at least 4 cities in the first two levels, as well as in the last two levels.

This means that we cannot have more than $2 + 2 + 92 \cdot \frac{3}{4} = 73$ levels, so the maximum possible level number is 72. But the level number is the number of flights required to reach a city at that level from the starting city. Since any of the 100 cities can be chosen as the starting city, this means that it is possible to travel from any city to any other in no more than 72 flights.