Expected steps to obtain a connected graph We have a country containing $N$ cities with no road between any two cities (what a poor country). Each day we choose two cities such that there is no road between them and build a road between them. We choose each pair of non-connected cities with equal probability. Let $X$ be the number of days until we obtain a connected country. What is the expected value of $X$?
A friend asked me, I have no idea yet.
 A: This is actually a classical result in the theory of random graphs.  The model you describe is known as the Erdos-Renyi random graph process $(G(n,M))_{M=0}^{n(n-1)/2}$: $G(n,0)$ is an empty graph on $n$ vertices; we obtain $G(n,M+1)$ from $G(n,M)$ by inserting a non-edge chosen uniformly at random.
In terms of marginal distribution, $G(n,M)$ is a graph on vertex set $[n]$ with $M$ edges, chosen with equal probability.
It was addressed in the paper that actually started the study of random graphs:

P. Erdos and A. Renyi. On Random Graphs I. Publicationes Mathematicae, 6:290-297, 1959.

The paper can be viewed online here.
The leading term in the expected number of edges to obtain connectivity is $\frac{1}{2}n\log n$. In fact, if
$$
M=\frac{n\log n+cn}{2},
$$
where $c=c(n)\rightarrow\infty$ as $n\rightarrow\infty$ (no matter how slowly), then the probability that $G(n,M)$ is connected tends to 1 with $n$. On the other hand, if $c=c(n)\rightarrow-\infty$ as $n\rightarrow\infty$, then the probability of connectedness tends to 0.
Why is $\frac{n\log n}{2}$ the threshold?  It turns out that this is the threshold for the property of having minimum degree 1... and that it is very unlikely for a graph to have minimum degree 1 and not be connected.
