Given a natural number . There are islands with bridges between them such that you can get from any island to any other island. One afternoon, a fire breaks out on one of the islands. Every morning, the fire spreads to all neighboring islands (those islands connected by a bridge). To control the fire, every night a bridge is blown up, as long as the fire still has room to spread. Let be the minimum number of bridges that must be blown up for a given group of islands and fire origin. Find the maximum of over all possible island groups and fire origins.
Solution
The answer is .
For , consider an archipelago with islands arranged in a grid, where the islands are connected row by row, and all islands in the leftmost column are also connected to the last island, where the fire starts. After rows, there are still rows where no bridge has been blown up. In such a row, the fire consumes the island the next morning. This means that after that morning, there is still an unburned bridge (towards the island) to blow up. Therefore, in this archipelago, you need to blow up at least bridges. By randomly adding islands to this group, we find that .
Now we describe a strategy that shows that for any archipelago, the minimum is also at most . In this strategy, we blow up a bridge each night to cut off the most islands from the fire. We then consider the situation by collapsing all the islands that are on fire into a single point and forgetting about the isolated islands. This way, we have a situation with one fire source but fewer islands. We then finish it off with induction towards .
The base case gives the only possibility , for which there is only one configuration and no bridges need to be blown up (since there are none). Assume as the induction hypothesis that in all groups with at most islands, at most bridges need to be blown up, and consider an archipelago with islands.
Suppose the fire source had a degree of : the island is connected to other islands via a bridge. Then, by the pigeonhole principle, there is a branch from the fire source with at least islands. In the morning, with this strategy, at least islands are removed by blowing up a bridge, and the fire then takes over islands. By collapsing these islands, we thus get a graph with a number of islands that is less than or equal to
where the first inequality follows from the arithmetic-geometric mean inequality: . Since the number of islands is an integer, it follows that there are at most islands. Therefore, the archipelago with islands needs to blow up bridges. This proves the induction step and thus concludes the proof.