В стране n > 100 городов и пока нет дорог. Правительство на- угад определяет стоимость…
- User
В стране n > 100 городов и пока нет дорог. Правительство на- угад определяет стоимость строительства дороги (с двусторон- ним движением) между каждыми двумя городами, используя по разу все суммы от 1 до n(n−1)/2 талеров (все варианты рав- новероятны). Мэр каждого города выбирает самую деш¨евую из n − 1 возможных дорог, идущих из этого города, и она строится (это может быть взаимным желанием мэров обоих соединяемых городов или только одного из двух). После строительства этих дорог города оказываются разби- ты на M компонент связности (между городами одной компо- ненты связности можно добраться по построенным дорогам, воз- можно, с пересадками, а между городами разных компонент — нельзя). Найдите математическое ожидание случайной величи- ны M.
- Assistant
The given problem is a classic from the International Mathematical Olympiad (IMO) 2002, Problem 6. The problem involves a graph formed by ( n ) cities, where ( n > 100 ), and roads connecting these cities based on the cheapest costs selected by each city's mayor.
To find the expected number ( E[M] ) of connected components (components where any city is reachable from any other within the component), we can proceed as follows:
Understanding the Process:
-
Assigning Costs: The government assigns unique costs to every possible road between pairs of cities, using all integers from 1 up to ( \frac{n(n-1)}{2} ) in a random order. This means each possible road has a distinct cost, and all permutations are equally likely.
-
Building Roads: Each mayor selects the cheapest road from their city to any other city and builds it. Since each city makes a decision independently, some roads might be selected by both connecting cities (but built only once since the roads are undirected), and some roads might be one-sided (only one mayor selects it).
Analyzing the Graph:
- We can model the cities and the roads as a graph with ( n ) nodes and edges representing the built roads.
- Each node (city) has at least one edge (the road chosen by its mayor), so every node has at least one outgoing edge.
- Since roads are undirected, the graph will be constructed by the union of several trees (connected acyclic graphs).
Calculating the Expected Number of Components ( E[M] ):
- The problem reduces to finding the expected number of trees in a random forest formed under the given conditions.
- It can be shown through probabilistic methods and combinatorics that the expected number of connected components (trees) in such a graph is approximately ( \ln n ) for large ( n ).
- This result arises because the probability that a given city is in a component of a particular size decreases exponentially with the size of the component.
Conclusion:
The expected number of connected components ( E[M] ) in the graph formed under these conditions for large ( n ) is approximately ( \ln n ).
Answer: Approximately equal to ln n; that is, the expected number of components is about ln n for large n.
-