# Probability Question: Bridge problem

There are $n$ islands in the ocean. Each island is linked by a single bridge between each and every unique pair of islands to ensure no island is isolated from the others. The probability of each bridge collapsed independently by earthquake is $p$. Suppose there is an earthquake causing some bridges to collapse - what is the probability of the remaining bridges are able to be traversed to each and every island?

I think we have $(n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}$ bridges and the remaining bridges in order to be able to be traversed to each and every island are at least $(n-1)$ bridges, so we have binomial probability and the probability of the event $(X)$ is $$P(X \ge n-1)=1-\sum_{k=0}^{n-2}\binom{\frac{n(n-1)}{2}}{k}p^k(1-p)^{\frac{n(n-1)}{2}-k}$$ Is my approach correct?

• That's not right. It's not enough that at least $(n-1)$ bridges survive $-$ they have to be the right bridges. I would be surprised if there was a simple formula for this. – TonyK Aug 24 '14 at 9:46
• @TonyK You are right. Now the problem becomes complicated – Venus Aug 24 '14 at 9:51
• – Henry Mar 31 at 10:42

Is my approach correct?

No, first because your $X$ seems to be both an event and a random variable (make up your choice), second because the fact that there remains at least $n-1$ bridges is necessary but not sufficient for every island to be connected to the others: with four islands called 1, 2, 3 and 4, the three bridges 1-2, 2-3 and 1-3 leave island 4 isolated.

• But we still can go to island 4 using route 1-2-3-4, can't we? – Venus Aug 24 '14 at 9:55
• @Venus: Yes -- bad example, Did! But the three bridges 1-2, 2-3, and 1-3 leave 4 isolated. – TonyK Aug 24 '14 at 9:57
• @TonyK You're right but how we determine the right bridges are still exist? – Venus Aug 24 '14 at 9:59
• Yes, bridges 1-2, 2-3 and 1-3. Sorry about the typo. – Did Aug 24 '14 at 10:20
• @Did Could you please take a look to my edited question? I really hope you can help me with this one. Thanks. – Venus Aug 24 '14 at 10:29