Problem

Source: 2021 Taiwan TST Round 3 Independent Study 1-C

Tags: combinatorics, Taiwan



A city is a point on the plane. Suppose there are $n\geq 2$ cities. Suppose that for each city $X$, there is another city $N(X)$ that is strictly closer to $X$ than all the other cities. The government builds a road connecting each city $X$ and its $N(X)$; no other roads have been built. Suppose we know that, starting from any city, we can reach any other city through a series of road. We call a city $Y$ suburban if it is $N(X)$ for some city $X$. Show that there are at least $(n-2)/4$ suburban cities. Proposed by usjl.