Browse · MathNet
PrintUkrajina 2008
Ukraine 2008 counting and probability
Problem
There are cities in a country. A monopoly company intends to establish air traffic between some of these cities. The government demands that the air traffic satisfies the following conditions. People should be able to get from each city to any other of these cities by one or several flights. Besides there must be an equal number of flights from each city. Note that two flights — from to and from to — are considered as one flight between cities and . Moreover, there may be at most one flight between two cities. But the company wants to cancel as little flights as possible so that you can not get from each city to any other city. What minimal number of flights has the company to cancel if: a) ; b) ?
Solution
a) Let's divide all the cities into two groups consisting of and cities respectively. Let's connect all the cities in each group in cycle. Thus, we obtain the degree of each vertex. Next lets select one city in each component and connect the two cities with a flight "007". Let's connect the rest of the cities with additional diagonals inside the group so that the degree of each vertex is (fig.5). It's clear that you just have to cancel flight "007" and the problem is solved. Thus, we obtain answer .
Fig.5
By contrary let us assume that . If you exclude this flight, the system falls into two groups of connected cities. In one of these groups there are cities, i.e. even number of cities. If the degree of each vertex was before we excluded the flight, in all there would be flights in this group. But this is not an integer as it should be.
b) Let this minimum be . It's obvious that . To prove this you just have to connect the cities in any cycle. It means that there are only two flights from each city. Thus, if you exclude any two flights, the system falls into two groups of cities, which are not connected between each other. Let's show that in this case .
Fig.5
By contrary let us assume that . If you exclude this flight, the system falls into two groups of connected cities. In one of these groups there are cities, i.e. even number of cities. If the degree of each vertex was before we excluded the flight, in all there would be flights in this group. But this is not an integer as it should be.
b) Let this minimum be . It's obvious that . To prove this you just have to connect the cities in any cycle. It means that there are only two flights from each city. Thus, if you exclude any two flights, the system falls into two groups of cities, which are not connected between each other. Let's show that in this case .
Final answer
a) 1; b) 2
Techniques
Menger's theorem / max-flow, min-cutCounting two waysInvariants / monovariants