## Problem 4

King George has decided to connect the 1680 islands in his kingdom by bridges. Unfortunately the rebel movement will destroy two bridges after all the bridges have been built, but not two bridges from the same island.

What is the minimal number of bridges the King has to build in order to make sure that it is still possible to travel by bridges between any two of the 1680 islands after the rebel movement has destroyed two bridges?


Solution 4 Answer: 2016

An island cannot be connected with just one bridge, since this bridge could be destroyed. Consider the case of two islands, each with only two bridges, connected by a bridge. (It is not possible that they are connected with two bridges, since then they would be isolated from the other islands no matter what.) If they are also connected to two separate islands, then they would be isolated if the rebel movement destroys the two bridges from these islands not connecting the two. So the two bridges not connecting them must go to the same island. That third island must have at least two other bridges, otherwise the rebel movement could cut off these three islands.

Suppose there is a pair of islands with exactly two bridges that are connected to each other. From the above it is easy to see that removing the pair (and the three bridges connected to them) must leave a set of islands with the same properties. Continue removing such pairs, until there are none left. (Note that the reduced set of islands could have a new such pair and that also needs to be removed.) Suppose we are left with $n$ islands and since two islands are removed at a time, $n$ must be an even number. And from the argument above it is clear that $n \geq 4$.

Consider the remaining set of islands and let $x$ be the number of islands with exactly two bridges (which now are not connected to each other). Then $n-x$ islands have at least three bridges each. Let $B^{\prime}$ be the number of bridges in the reduced set. Now $B^{\prime} \geq 2 x$ and $2 B^{\prime} \geq 2 x+3(n-x)=3 n-x$. Hence $2 B^{\prime} \geq \max (4 x, 3 n-x) \geq 4 \cdot \frac{3 n}{5}$, and thus $B^{\prime} \geq \frac{6 n}{5}$. Now let $B$ be the number of bridges in the original set. Then

$$
B=B^{\prime}+3 \cdot \frac{1680-n}{2} \geq \frac{6 n}{5}+\frac{6(1680-n)}{4} \geq \frac{6 \cdot 1680}{5}=2016
$$

It is possible to construct an example with exactly 2016 bridges: Take 672 of the islands and number them $0,1,2, \ldots 671$. Connect island number $i$ with the islands numbered $i-1$, $i+1$ and $i+336$ (modulo 672). This gives 1008 bridges. We now have a circular path of 672 bridges: $0-1-2-\cdots-671-0$. If one of these 672 bridges are destroyed, the 672 islands are still connected. If two of these bridges are destroyed, the path is broken into two parts. Let $i$ be an island on the shortest path (if they have the same length, just pick a random one). Then island $i+336$ (modulo 672) must be on the other part of the path, and the bridge connecting these two islands will connect the two paths. Hence no matter which two bridges the rebel movement destroys, it is possible to travel between any of the 672 islands.

Now for every of the 1008 bridges above, replace it with two bridges with a new island between the two. This increases the number of bridges to 2016 and the number of islands to $672+1008=1680$ completing the construction. Since the rebel movement does not destroy two bridges from the same island, the same argument as above shows that with this construction it is possible to travel between any of the 1680 islands after the destruction of the two bridges.

