
Problem 11.3. There are 2001 towns in a country every one of which is connected with at least 1600 towns by direct bus line. Find the largest $n$ for which there exist $n$ towns any two of which are connected by direct bus line.


Solution: Let $S_{1}$ snd $S_{1}$ be two towns connected by direct bus line. If $k$ is the number of towns connected to both $S_{1}$ and $S_{2}$ by bus line then $(1599-k)+(1599-k)+k \leq 1999$ which implies that $k \geq 1198$. Therefore there exists town $S_{3}$ connected to both $S_{1}$ and $S_{2}$. Further, let $k$ be the number of towns connected to all $S_{1}, S_{2}$ and $S_{3}$. Therefore $(1197-k)+(1598-k)+k \leq 1998$, so giving $k \geq 797$. Therefore there exists town $S_{4}$ connected to all $S_{1}, S_{2}$ and $S_{3}$. By analogy let $k$ be the number of towns connected to all $S_{1}, S_{2}, S_{3}$ and $S_{4}$. We have $(796-k)+(1597-k)+k \leq 1997$, which implies $k \geq 396$. Therefore there exists $S_{5}$ connected to all $S_{1}, S_{2}, S_{3}$ and $S_{4}$. For the number $n$ from the condition of the problem we obtain $n \geq 5$. We show that $n=5$. For, number the towns by $S_{1}, S_{2}, \ldots, S_{2001}$ and connect $S_{k}$ and $S_{m}$ with direct line for all $k$ and $m$ for which $k \not \equiv m(\bmod 5)$. Since $\left[\frac{2001}{5}\right]=400$, we have that each town is connested to 1600 or 1601 other towns, i.e. the condition of the problem is satisfied.

For arbitrary 6 towns the numbers of at least two are equal modulo 5 and therefore they are not connected to each other. Therefore $n<6$ and so $n=5$.

## L National Mathematics Olympiad 3rd round, 28-29 April 2001
