MathDB
Nearest Neighbor on a Plane

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

May 1, 2021
combinatoricsTaiwan

Problem Statement

A city is a point on the plane. Suppose there are n≥2n\geq 2 cities. Suppose that for each city XX, there is another city N(X)N(X) that is strictly closer to XX than all the other cities. The government builds a road connecting each city XX and its N(X)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 YY suburban if it is N(X)N(X) for some city XX. Show that there are at least (n−2)/4(n-2)/4 suburban cities.
Proposed by usjl.
Back to ProblemsView on AoPS