Berkeley Math Circle Monthly Contest 2

Solution:

Consider the city $C_{\max}$ with the maximal population $M$ (breaking ties arbitrarily). Then $M$ is the average of the populations of the neighboring cities, say $p_{1}, p_{2}, \ldots, p_{n}$, meaning that
$$\frac{p_{1}+p_{2}+\cdots+p_{n}}{n}=M$$
But $p_{1}, p_{2}, \ldots, p_{n} \leq M$, and hence $p_{1}+p_{2}+\cdots+p_{n} \leq n M$. So this can only occur if $p_{1}=p_{2}=\cdots=p_{n}=M$. Hence all neighbors of $C_{\max}$ have population $M$.

Proceeding in the same fashion, we find that all neighbors of neighbors of $C_{\max}$ also must have population $M$, and so on. Because the network of cities is connected, this implies that all cities must have population $M$.