jump to navigation

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.


no comments yet - be the first?