Problem:
You would like to provide airline service to the 10 cities in the nation of Schizophrenia, by instituting a certain number of two-way routes between cities. Unfortunately, the government is about to divide Schizophrenia into two warring countries of five cities each, and you don't know which cities will be in each new country. All airplane service between the two new countries will be discontinued. However, you want to make sure that you set up your routes so that, for any two cities in the same new country, it will be possible to get from one city to the other (without leaving the country).
What is the minimum number of routes you must set up to be assured of doing this, no matter how the government divides up the country?
Solution
Solution:
Each city must be directly connected to at least 6 other cities, since otherwise the government could put in one country and all its connecting cities in the other country, and there would be no way out of . This means that we have 6 routes for each of 10 cities, counted twice (since each route has two endpoints) routes. On the other hand, this is enough: picture the cities arranged around a circle, and each city connected to its 3 closest neighbors in either direction. Then if and are in the same country but mutually inaccessible, this means that on each arc of the circle between and , there must be (at least) three consecutive cities in the other country. Then this second country would have 6 cities, which is impossible. So our arrangement achieves the goal with 30 routes.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.