CIS

Combinatorics Difficulty 6.5 National Olympiad Prove it Soviet Union

Problem:

A country contains $n$ cities and some towns. There is at most one road between each pair of towns and at most one road between each town and each city, but all the towns and cities are connected, directly or indirectly. We call a route between a city and a town a gold route if there is no other route between them which passes through fewer towns. Show that we can divide the towns and cities between $n$ republics, so that each belongs to just one republic, each republic has just one city, and each republic contains all the towns on at least one of the gold routes between each of its towns and its city.

Solution

Solution:

Let the cities be $C_1$ , $C_2$ , ..., $C_n$ . For each town $T$ take the shortest path from $T$ to a city. If there are shortest paths to more than one city, then take one to the city with the smallest index. We assign $T$ to that city.

Now suppose $T$ is assigned to $C_i$ . Let $G$ be a gold route from $T$ to $C_i$ of length $n$ . Suppose $T'$ is another town on $G$ . Note that $T'$ cannot be a city, or $T$ would be assigned to $T'$ , not $C_i$ . Suppose the part of $G$ between $T'$ and $C_i$ has length $k$ . There cannot be a path from $T'$ to any city of length $< k$ , otherwise we would have a path from $T$ to a city shorter than $n$ . Nor can there be a path of length $k$ from $T'$ to $C_j$ with $j < i$ , otherwise there would be a path of length $n$ from $T$ to $C_j$ and $T$ should be assigned to $C_j$ . Hence $T'$ is also assigned to $C_i$ , as required.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.