A probability puzzle about mountain villages I hope this puzzle will be of some interest.
The mountain villages $A,B,C$ and $D$ lie at the vertices of a tetrahedron, and each pair of villages is joined by a road. After a snowfall the probability that any road is blocked is $p$, and
is independent of the conditions of any other road. The probability that, after a snowfall, it is possible to travel from any village to any other village by some route is $P$.
What is $P$ in terms of the probability $p$?
 A: Let's assume $K_4$ instead of an actual tetrahedron, since I'm envisioning some serious avalanches here. :-)
There are six roads in all.  If at most two roads are open, then at least one village cannot be reached, since two roads can only connect three villages.  If at most two roads are closed, then all villages can be reached, since no two roads can isolate a village.
Therefore, the only interesting cases are when three roads are closed, and three are open.  There are three possible configurations for three open roads: triangle (four configurations), Y (four), and single-path (twelve).  Of these, only the triangle configuration fails to connect all villages.
Thus, the probability that the villages are connected is
\begin{align}
P & = Pr(\text{at least four roads are open, or three roads are open, not in triangle formation}) \\
  & = \binom{6}{6}(1-p)^6 + \binom{6}{5}p(1-p)^5 + \binom{6}{4}p^2(1-p)^4
    + (12+4)p^3(1-p)^3 \\
  & = (1-p)^6+6p(1-p)^5+15p^2(1-p)^4+16p^3(1-p)^3 \\
  & = 1-4p^3-3p^4+12p^5-6p^6
\end{align}
If $p = 1/2$, for example, $P = 19/32$.
