In a city, every bus route has 3 stops, there is a bus route between any two stops, and any two bus routes have 1 common stop. How many bus routes can there be in the city? (H)
Let the number of stops be denoted by $n$. Then the number of stop pairs is $\binom{n}{2}$. We know that there is a bus route between any two stops, and that any two bus routes have exactly 1 common stop, so there is exactly one bus route between any two stops. Since every bus route has 3 stops, the number of bus routes is $\frac{1}{3} \cdot \binom{n}{2} = \frac{n(n-1)}{6}$, and thus the number of common stops for pairs of routes is

$$
k = \binom{\frac{n(n-1)}{6}}{2} = \frac{\frac{n(n-1)}{6} \left(\frac{n(n-1)}{6} - 1\right)}{2}
$$

On the other hand, at each stop, $\frac{n-1}{2}$ bus routes stop (each bus route has 2 other stops), so each stop corresponds to $\binom{\frac{(n-1)}{2}}{2} = \frac{\frac{n-1}{2} \cdot \left(\frac{n-1}{2} - 1\right)}{2}$ common stops. Therefore, $k = n \cdot \frac{\frac{n-1}{2} \left(\frac{n-1}{2} - 1\right)}{2}$, which means

$$
\frac{\frac{n(n-1)}{6} \cdot \left(\frac{n(n-1)}{6} - 1\right)}{2} = n \cdot \frac{\frac{n-1}{2} \left(\frac{n-1}{2} - 1\right)}{2}
$$

From this, we get $n^2 - 10n + 21 = 0$, which gives $n = 3$ or $n = 7$.

In the case of $n = 3$, there is 1 bus route, for which the statement of the problem is obviously true. In the case of $n = 7$, there are 7 bus routes, for which the following example can be given:

If the bus stops are labeled $1, 2, 3, \ldots, 7$, then the following bus routes satisfy the conditions of the problem:

$$
\begin{gathered}
\{1,2,3\}, \quad\{1,4,5\}, \quad\{1,6,7\}, \quad\{2,4,6\} \\
\{2,5,7\}, \quad\{3,4,7\}, \quad\{3,5,6\}
\end{gathered}
$$

Therefore, there can be 1 or 7 bus routes in the city.

Gábor Székelyhidi (Kuwait, New English School, 11th grade)

Note. The grouping of stops into routes in the problem is a special case of the following type of configurations. Consider a set with $n$ elements and certain subsets of this set with the following two properties:

(1) Any two (different) such subsets have exactly one common element; and

(2) For any two (different) elements in the set, there is exactly one selected subset that contains both of them.

Configurations that satisfy properties (1) and (2) - except for certain trivial arrangements - are called finite projective planes; the elements of the set are called points, and the selected subsets are called lines. It is easy to show that the number of lines in a projective plane is the same as the number of points, i.e., $n$. It is also not difficult to prove that every line has the same number of points - this number is usually denoted by $(q+1)$ - and this number is equal to the number of lines passing through any given point. It then follows easily that $n = q^2 + q + 1$.

Using finite fields, it is possible to construct finite projective planes for every case where $q$ is a prime power. However, there are planes that cannot be constructed using this general method. No one has yet found a plane in which $q$ is not a prime power. This is related to a famous, unsolved problem in finite mathematics: for which values of $q$ does a finite projective plane of order $q$ exist (can $q$ be anything other than a prime power)?

![](https://cdn.mathpix.com/cropped/2024_05_02_d3c5ce393a10cdc3022fg-1.jpg?height=317&width=339&top_left_y=2042&top_left_x=882)