Archipelago

A graph theory problem from the Riddler blog. Here it goes:

You live on the volcanic archipelago of Riddleria. Your archipelago is connected via a network of bridges, forming one unified community. In an effort to conserve resources, the ancient Riddlerians who built this network opted not to build bridges between any two islands that were already connected to the community otherwise. Hence, there is exactly one path from any one island to any other island.

Each island contains exactly one volcano. You know that if a volcano erupts, the subterranean pressure change will be so great that the volcano will collapse in on itself, causing its island — and any connected bridges — to crumble into the ocean. Remarkably, other islands will be spared unless their own volcanoes erupt. But if enough bridges go down, your once-unified archipelagic community could split into several smaller, disjointed communities.

If there were N islands in the archipelago originally and each volcano erupts independently with probability p, how many disjointed communities can you expect to find when you return? What value of p maximizes this number?

Here is my solution:
[Show Solution]

One thought on “Archipelago”

  1. Neat! I reached the same answer with a very different method, considering the original spanning tree, picking an arbitrary node as the root, creating indicator random variables for each node (1 if it’s a root in the post-eruption spanning forest, zero if not), and using linearity of expectation. The only wrinkle is that you have to take special care with the root of the original tree. But it’s nice in that you can think only about the vertices. 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *