Broken Bridges

John lives in the Trees of Ten Houses, and it is a most ideal and idyllic place for him and the other dwellers up in the canopy. They have invested a tremendous amount of time in engineering these houses, and to ensure no house felt isolated from the others, they built a fresh, finely crafted bridge between each and every house!

Unfortunately, the Trees of Ten Houses were not immune to thunderstorms, nor were the bridges well engineered. The night was treacherous, howling with wind and freezing with rain, so the odds for the bridges were not good--each bridge seemed just as likely to survive as to be shattered!

Fortunately, as there were so very many bridges in the Trees of Ten Houses, when John did wake the following morning, he found he was able to make his way to each and every house using only the existing bridges, though round-about routes may have been necessary. As they began rebuilding, John became curious... what were the chances that they'd all be so lucky? More formally, if \(P\) is the probability that, after the storm, John is able to traverse to each and every house, what is \(\left\lfloor 10^{10} P \right\rfloor\)?

Details and Assumptions:

  • The Trees of Ten Houses do, in fact, contain precisely 10 houses.
  • Before the storm, there exists a single bridge between each and every unique pair of houses.
  • The storm destroys each bridge with independent probability \(\frac{1}{2}\).
  • John is allowed to traverse through others' houses to try to reach all of them, but he must only use the surviving bridges to get there. No vine swinging allowed.

Tagged under #ComputerScience as this problem is quite tedious to do without it, though not impossible.
Image Credit:

Problem Loading...

Note Loading...

Set Loading...