There are islands, where . A ferry company establishes routes between certain pairs of islands, such that whenever we divide these islands into two nonempty groups, we can always find one island from each group such that there is a route between these two islands. At the end of each year, the company will select islands and that are connected by a route, and close the route between them. At the same time, for all other islands , if has a route to but not to , then the company will add a route between and ; conversely, if has a route to but not to , then the company will add a route between and .
For two groups of islands and , if and , then we say the route connecting and links and . Suppose we know that, at any point in time, if we divide these islands into two nonempty groups, then the company will necessarily, within some number of years, close a route linking these two groups. Prove that: after some number of years, there will be an island that has a route to every other island.
Solution
We say that two groups of islands and form a network if and only if for any and , there is a route between and .
1. First choose any route, and let its endpoints be islands and . Since , there must exist a third island ; and by the assumption of the problem, it must be connected to or , so without loss of generality assume it is connected to . Define , ; it is easy to see that forms a network. Note that .
2. Next we prove that: if , then in every year, we can always redivide into two nonempty groups of islands and , such that forms a network.
If the route closed by the company does not link and , then we may simply keep the original grouping. Now suppose the company has closed some route linking and . Let us consider and ; it is easy to see that , and both and are nonempty (since ).
Below we show that forms a network. Consider ; since forms a network, there must be a route between and . If there was originally no route between and ,
then when is closed at the end of the year, must be established. In other words, must have a connection to both and . Similarly, for all , must have a connection to both and . This means that any island in has a connection to both and , so forms a network. This completes the proof.
3. Suppose . We now prove that: after some number of years, we can find an island not in , and redivide into two nonempty groups of islands and , such that forms a network.
Let . By the assumption of the problem, after some number of years, the company must close the route between and some island in , without loss of generality say it is . Note that forms a network, so all points in have a route to ; therefore, when is closed, all points in will have a route to . Therefore, consider , , then forms a network and . This completes the proof.
4. By 3., we may assume that after some number of years, we can divide all islands into two nonempty groups of islands and , such that forms a network. Now suppose that after some number of years, the route between and is closed. Let , and let be all the other islands, then it is easy to see that forms a network.
Suppose that after some further number of years, without loss of generality, the route between and some is closed. Since has a route to all islands in , this means that when is closed, will be established, that is, has a route to every other island. This completes the proof.