In a communication system consisting of 2001 subscribers, each subscriber is connected to exactly $n$ others. Determine all possible values of $n$.

#
Calculate the number of pairs of connected subscribers and show that $n$ is even.

## Solution

Since each of the 2001 subscribers is connected to exactly $n$ others, the total number of connection directions is $2001n$. Therefore, the total number of connected pairs of subscribers is $2001n / 2$, since each connected pair has exactly two connection directions. Since this number must be an integer, the number $n$ must be even.

We will prove that for each $n = 2t$ ($t = 0, 1, \ldots, 1000$), there exists a communication system with 2001 subscribers where each is connected to exactly $n$ others. Indeed, by placing all subscribers on a circle and connecting each of them to the $t$ nearest neighbors in the clockwise direction and to the $t$ nearest neighbors in the counterclockwise direction, we obtain an example of such a communication network.