HMMT 二月 2004 · 冲刺赛 · 第 40 题

英文解析

40. 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, thegovernment is about to divide Schizophrenia into two warring countries of five citieseach, and you don’t know which cities will be in each new country. All airplane service 13
    between the two new countries will be discontinued. However, you want to make surethat 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: 30
    Each city C must be directly connected to at least 6 other cities, since otherwisethe government could put C in one country and all its connecting cities in the othercountry, and there would be no way out of C . This means that we have 6 routes foreach of 10 cities, counted twice (since each route has two endpoints) ⇒ 6 · 10 / 2 = 30
    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 C and Dare in the same country but mutually inaccessible, this means that on each arc of the circle between C and D , there must be (at least) three consecutive cities in the othercountry. Then this second country would have 6 cities, which is impossible. So ourarrangement achieves the goal with 30 routes.