## Problem of the Day #102: Billy’s Cities
*June 29, 2011*

*Posted by Sreenath in : potd , trackback*

Billy is in charge of creating plans for roads between a number of cities. To create a plan for $n$ cities, he flips a coin for each of the $\binom{n}{2}$ possible roads. If it lands heads, he builds the road, and if it lands tails, he doesn’t. A plan is considered *acceptable* if for every choice of two cities, there exists a path between them (can go through other cities). If Billy creates $4620$ plans for $3$ cities using this method, compute the expected value of the number of acceptable plans.

## Comments»

no comments yet - be the first?