Question 180
NASA has proposed populating Mars with $2,004$ settlements. The only way to get from one settlement to another will be by a connecting tunnel. A bored bureaucrat draws on a map of Mars, randomly placing $N$ tunnels connecting the settlements in such a way that no two settlements have more than one tunnel connecting them. What is the smallest value of $N$ that guarantees that, no matter how the tunnels are drawn, it will be possible to travel between any two settlements?