Track / Stage 6 / 40 of 400 #1040 of 1964

Problem 1040

National olympiad, first round

Algebra Difficulty 6.0 Prove it

On a distant planet, there are 2014 cities, some pairs of which are connected by two-way roads. It turns out that the population of each city is the average of the populations of the cities to which it is connected by a single road, and moreover that it is possible to travel from every city to every other city by a sequence of roads.

Prove that all cities have the same population.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.