Izmeystiev I.V.

The network of bus routes in the suburb of Amsterdam is organized in such a way that:

a) each route has exactly three stops;

b) any two routes either have no common stops at all or have only one common stop. What is the maximum number of routes that can be in this suburb if there are a total of 9 stops?
Evaluation. Consider some stop A. Determine the maximum number of routes passing through it. Besides A, there are 8 other stops in the city. On each route passing through A, there are two more stops. Since no two of these routes can have common stops other than A, a total of no more than 8 / 2 = 4 routes can pass through A. Number all the stops and denote by \(a_{1}\) the number of routes passing through the first stop, by \(a_{2}\) the number of routes passing through the second stop, ..., and by \(a_{9}\) the number of routes passing through the ninth stop. Since each route has exactly 3 stops, \(a_{1} + \ldots + a_{9} = 3n\), where \(n\) is the total number of routes. According to the above proof, each term is no more than four. Therefore, \(3n < 4 \cdot 9 = 36\), which means \(n < 12\).

Example. The diagram below shows a scheme that satisfies the problem's conditions and contains 12 routes.

![](https://cdn.mathpix.com/cropped/2024_05_06_f579c76dfb5bc127b163g-40.jpg?height=798&width=987&top_left_y=1&top_left_x=547)

## Answer

12 routes.

Submit a comment