redacted

Tintarn wrote: In a country there are $n>100$ cities and initially no roads. The government randomly determined the cost of building a two-way road between any two cities, using all amounts from $1$ to $\frac{n(n-1)}{2}$ thalers once (all options are equally likely). The mayor of each city chooses the cheapest of the $n-1$ roads emanating from that city and it is built (this may be the mutual desired of the mayors of both cities being connected, or only one of the two). After the construction of these roads, the cities are divided into $M$ connected components (between cities of the same connected component, you can get along the constructed roads, possibly via other cities, but this is not possible for cities of different components). Find the expected value of the random variable $M$. Proposed by F. Petrov The resulting graph is cycle-free. $n$ edges are chosen, some of them twice. This is the case iff it is the cheapest of the $2n-3$ streets adjacant to its both ends. So the expected value of streets chosen twice is $\frac{n(n-1)}{2(2n-3)}$. But the number of connected components is the number of edges chosen twice. So the expected value of $M$ is $\frac{n(n-1)}{2(2n-3)}$.

Take the graph interpretation with a total ordering $<$ on its edges. Let the graph be $G$. Claim. $G$ is cycle-free. Proof. Assume for the sake of contradiction there is a cycle $v_1v_2,\ldots,v_k,v_1$. WLOG the mayor at $v_i$ chose the edge $v_iv_{i+1}$ (with indices taken cyclically). Then $v_kv_1>v_1v_2>v_2v_3>\cdots>v_{k-1}v_k>v_kv_1$, a contradiction. $\square$ Thus $M=n-||G||$. It can be shown that the probability a given edge $e$ is chosen is \[ \frac{1}{(2n-3)\binom{2n-4}{n-2}}\left(\binom{2n-4}{n-2}+\sum_{k=2}^{2n-3}2\binom{2n-3-k}{n-2}\right)=\frac{3n-5}{(n-1)(2n-3)}. \]Thus $E[M]=n-\frac{3n-5}{(n-1)(2n-3)}\binom{n}{2}=\boxed{\frac{n(n-1)}{4n-6}}$. $\square$