2016 IMO Shortlist C6

There are $n \geq 3$ islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route. After each year, the ferry company will close a ferry route between some two islands $X$ and $Y$. At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected by a ferry route to exactly one of $X$ and $Y$, a new route between this island and the other of $X$ and $Y$ is added. Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.

一座城市中有 $n \geq 3$ 个岛屿。最初，渡轮公司在某些对岛屿之间提供一些航线，因此不可能将岛屿分为两组，使得不同组中的两个岛屿没有渡轮路线连接。每年之后，渡轮公司都会关闭 $X$ 和 $Y$ 两个岛屿之间的渡轮航线。同时，为了维持服务，公司将按照以下规则开辟新航线：对于任何通过轮渡航线连接到$X$和$Y$中的一个岛屿的岛屿，在该岛屿和$X$和$Y$中的另一个岛屿之间增加一条新航线。假设在任何时刻，如果我们以任何方式将所有岛屿分成两个非空的组，那么众所周知，轮渡公司将在几年后关闭连接这两个组中的两个岛屿的某条航线。证明几年后将会有一个岛屿通过渡轮路线与所有其他岛屿相连。