Drawing lines on a map

Question

This was a puzzle that appeared in an old math contest as well as an unrelated puzzle book.

Suppose we have a two-dimensional map with a lot of cities marked on it. For each city on the map, we draw a line segment to the city nearest to it (we assume that there is always a nearest city and that no two cities are exactly the same distance apart from any third city). Prove that no city will have more than five line segments connected to it.

I seem to remember that the proof involved triangles, but to this day don't know the whole proof.

Answer 1

I'll assume the cities lie on a flat plane, which seems to be the most reasonable interpretation of the question.

Let's assume (for contradiction) that we had a city which is connected to at least 6 other cities. First, note that this implies that no two cities lie on the same ray extending outwards from the central city which I'll label as $0$. Picking the closest of these six cities to be $1$ and label the cities counterclockwise starting from the ray $\vec{01}$ as $2,3, \ldots, 6$. Now $0$ and $1$ are connected since $1$ is closest to $0$. For cities $2, \ldots, 6$, the only way they can be connected to $0$ is by being closer to $0$ than they are to any other city. Here's a conceptual diagram:

First, let's deal with the two triangles $\Delta012$ and $\Delta 061$ which have city 1 as vertices. By construction, $d(0,1) < d(0,2)$, where $d(i,j)$ is the distance from $i$ to $j$. $1$ already has a segment connecting it to $0$ since it's the closest city to $0$. But for $2$, since it isn't the closest city to $0$, we need $0$ to be the closest city to it. So $d(0,2) < d(1,2)$. By transitivity, $d(0,1) < d(1,2)$, so the longest edge in $\Delta 012$ is $\overline{12}$. The same logic shows that the longest edge in $\Delta 061$ is $\overline{16}$.

Now, for $\Delta 023$, we know that $d(0,2) < d(2,3)$ and similarly $d(0,3) < d(2,3)$, both since $2$ and $3$ each have $0$ as their closest city. Hence, the longest edge of the triangle $\Delta 023$ is $\overline{23}$. We apply the same to $\Delta 034, \Delta 045, \Delta 056$ to show that the side opposite the angle at city $0$ is always the longest. This is thus true for all 6 triangles.

The law of sines tells us that either the largest side is opposite the largest angle, or else the "triangle" has a reflex angle (an angle greater than $180 ^\circ$). It's possible that $\angle 102$ is a reflex angle, but by construction it's not possible for either of the other angles to be a reflex angle, because we chose them to lie on rays going outwards from $0$, and there's no way to create a reflex angle between the two rays.

So either $\angle 102$ is the largest angle in the triangle, making it more than $60 ^\circ$, or it's more than $180 ^\circ$, which would of course still make it more than $60 ^\circ$. We can apply the same logic for $\Delta 023, \Delta034, \ldots, \Delta061$ and find that the central city has 6 angles each of over $60 ^\circ$, which means that the total angle is more than $360 ^\circ$. That's a contradiction since we know it has to be exactly $360 ^\circ$ by construction.

Hence, it's impossible for any city to be connected to 6 other cities this way.

Answer 2

I'm not sure this is rigorous per se, but I think it's accurate.

Consider some number cities arranged in a circle of radius $r$ around a central city (the "most connected"). The furthest these can be from each other is when they are distributed equally. When there are six cities around the circle, they are all at a distance $r$ from each other. Since each of the cities has exactly one closest city, there cannot be six cities around the circle. If there were more, they would be closer to each other than the central one, so there are strictly less than six cities closest to a single one; since we're working in integers, that means at most five.