MathDB

560

Part of 1992 All Soviet Union Mathematical Olympiad

Problems(1)

ASU 560 Commonwealth of Independent States 1992 n cities, gold route

Source:

8/14/2019
A country contains nn 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 nn 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.
combinatorics