已知一座城市有 $n$（$n\geqslant 3$）个岛．最初时，渡船公司提供一些岛与岛之间的航线，满足不能将这 $n$ 个岛拆分成两个子集，使得任意在不同子集中的两个岛之间没有航线．以后每年，渡船公司将关闭某两个岛 $X$ 与 $Y$ 之间的航线，同时为了保持所提供的服务，渡船公司将根据规则开通一些新的航线：对于任意恰与 $X,Y$ 之一有航线的岛，则渡船公司开通一条这个岛与 $X,Y$ 之外的一个岛之间的新的航线．
假设在某一时刻，若以任意方式将这 $n$ 个岛拆分为两个非空子集，则已知某年后渡船公司关闭一条连接属于两个不同子集的两个岛之间的航线．证明：一些年后，存在一个岛与其他所有岛之间均有航线．
假设在某一时刻，若以任意方式将这 $n$ 个岛拆分为两个非空子集，则已知某年后渡船公司关闭一条连接属于两个不同子集的两个岛之间的航线．证明：一些年后，存在一个岛与其他所有岛之间均有航线．
【难度】
【出处】
2016IMO Short List
【标注】
【答案】
最初时，选取任意有航线连接的两个岛 $A,B$，将岛 $A$ 放入集合 $\mathscr{A}$，将岛 $B$ 放入集合 $\mathscr{B}$．由条件，知一定有另外一个岛与岛 $A,B$ 之一有航线．不失一般性，不妨假设这个岛 $C$ 与岛 $A$ 之间有航线．将岛 $C$ 放入集合 $\mathscr{B}$．
若一个集合中的每个岛均与另一个集合中的每个岛之间有航线，则称这两个岛的集合构成一个"网络"．
下面证明：所有的岛一个接一个地被放入集合 $\mathscr{A}\cap\mathscr{B}$．
假设集合 $\mathscr{A}$ 与 $\mathscr{B}$ 构成一个网络，且 $3\leqslant|\mathscr{A}\cup\mathscr{B}|<n$．当 $A\in\mathscr{A}$，$B\in\mathscr{B}$，且岛 $A,B$ 之间的航线被关闭后，这种关系不再成立．此时，定义 $\mathscr{A}'=\{A,B\}$，$\mathscr{B}'=(\mathscr{A}\cup\mathscr{B})-\{A,B\}$．则集合 $\mathscr{B}'$ 是非空的．
考虑任意的 $C\in\mathscr{A}-\{A\}$．由集合 $\mathscr{A}$ 与 $\mathscr{B}$ 的关系，知岛 $C$ 与 $B$ 之间有航线．若关闭岛 $A$ 与 $B$ 之间的航线之前岛 $C$ 与 $A$ 之间没有航线，则关闭岛 $A$ 与 $B$ 之间的航线之后开通岛 $C$ 与 $A$ 之间的航线．于是，岛 $C$ 与 $A$ 和 $B$ 之间均有航线联结．对于集合 $\mathscr{B}-\{B\}$ 中的任意一个岛，也有同样的结论．从而，集合 $\mathscr{A}'$ 与 $\mathscr{B}'$ 构成网络，且 $\mathscr{A}'\cup\mathscr{B}'=\mathscr{A}\cup\mathscr{B}$．因此，这些岛总能被拆分成集合 $\mathscr{A},\mathscr{B}$，使得 $\mathscr{A}$ 与 $\mathscr{B}$ 构成网络．
由于 $|\mathscr{A}\cup\mathscr{B}|<n$，则存在一些岛不属于 $\mathscr{A}\cup\mathscr{B}$．由条件，知一些年后一定有一个岛 $A\in\mathscr{A}\cup\mathscr{B}$ 和一个岛 $D\notin\mathscr{A}\cup\mathscr{B}$，这两个岛之间的航线被关闭．不失一般性，不妨假设 $A\in\mathscr{A}$．则集合 $\mathscr{B}$ 中的每个岛（无论之前否与岛 $D$ 有航线）均与岛 $D$ 之间有航线．于是，可以将岛 $D$ 放入集合 $\mathscr{A}$．从而，得到新的集合 $\mathscr{A}$ 和 $\mathscr{B}$，且 $\mathscr{A}$ 和 $\mathscr{B}$ 仍然构成网络．同时，$|\mathscr{A}\cup\mathscr{B}|$ 的值增加了 $1$．
用同样的方式可使集合 $\mathscr{A}\cup\mathscr{B}$ 中的元素的个数不断增加，最后的 $\mathscr{A}\cup\mathscr{B}$ 包含了所有的岛．因此，可以假设 $|\mathscr{A}\cup\mathscr{B}|=n$．
假设一些年后 $A\in\mathscr{A}$ 和 $B\in\mathscr{B}$ 之间的航线被关闭，则将岛 $A$ 和 $B$ 放人集合 $\mathscr{A}'$，剩下的岛放入集合 $\mathscr{B}'$．故 $\mathscr{A}'$ 与 $\mathscr{B}'$ 构成网络．当岛 $A$ 与 $C\in\mathscr{B}$ 之间的航线被关闭后，这种关系不再成立．
因此，这种情况最终一定会发生，此时，岛 $B$ 将同其他所有岛之间均有航线
若一个集合中的每个岛均与另一个集合中的每个岛之间有航线，则称这两个岛的集合构成一个"网络"．
下面证明：所有的岛一个接一个地被放入集合 $\mathscr{A}\cap\mathscr{B}$．
假设集合 $\mathscr{A}$ 与 $\mathscr{B}$ 构成一个网络，且 $3\leqslant|\mathscr{A}\cup\mathscr{B}|<n$．当 $A\in\mathscr{A}$，$B\in\mathscr{B}$，且岛 $A,B$ 之间的航线被关闭后，这种关系不再成立．此时，定义 $\mathscr{A}'=\{A,B\}$，$\mathscr{B}'=(\mathscr{A}\cup\mathscr{B})-\{A,B\}$．则集合 $\mathscr{B}'$ 是非空的．
考虑任意的 $C\in\mathscr{A}-\{A\}$．由集合 $\mathscr{A}$ 与 $\mathscr{B}$ 的关系，知岛 $C$ 与 $B$ 之间有航线．若关闭岛 $A$ 与 $B$ 之间的航线之前岛 $C$ 与 $A$ 之间没有航线，则关闭岛 $A$ 与 $B$ 之间的航线之后开通岛 $C$ 与 $A$ 之间的航线．于是，岛 $C$ 与 $A$ 和 $B$ 之间均有航线联结．对于集合 $\mathscr{B}-\{B\}$ 中的任意一个岛，也有同样的结论．从而，集合 $\mathscr{A}'$ 与 $\mathscr{B}'$ 构成网络，且 $\mathscr{A}'\cup\mathscr{B}'=\mathscr{A}\cup\mathscr{B}$．因此，这些岛总能被拆分成集合 $\mathscr{A},\mathscr{B}$，使得 $\mathscr{A}$ 与 $\mathscr{B}$ 构成网络．
由于 $|\mathscr{A}\cup\mathscr{B}|<n$，则存在一些岛不属于 $\mathscr{A}\cup\mathscr{B}$．由条件，知一些年后一定有一个岛 $A\in\mathscr{A}\cup\mathscr{B}$ 和一个岛 $D\notin\mathscr{A}\cup\mathscr{B}$，这两个岛之间的航线被关闭．不失一般性，不妨假设 $A\in\mathscr{A}$．则集合 $\mathscr{B}$ 中的每个岛（无论之前否与岛 $D$ 有航线）均与岛 $D$ 之间有航线．于是，可以将岛 $D$ 放入集合 $\mathscr{A}$．从而，得到新的集合 $\mathscr{A}$ 和 $\mathscr{B}$，且 $\mathscr{A}$ 和 $\mathscr{B}$ 仍然构成网络．同时，$|\mathscr{A}\cup\mathscr{B}|$ 的值增加了 $1$．
用同样的方式可使集合 $\mathscr{A}\cup\mathscr{B}$ 中的元素的个数不断增加，最后的 $\mathscr{A}\cup\mathscr{B}$ 包含了所有的岛．因此，可以假设 $|\mathscr{A}\cup\mathscr{B}|=n$．
假设一些年后 $A\in\mathscr{A}$ 和 $B\in\mathscr{B}$ 之间的航线被关闭，则将岛 $A$ 和 $B$ 放人集合 $\mathscr{A}'$，剩下的岛放入集合 $\mathscr{B}'$．故 $\mathscr{A}'$ 与 $\mathscr{B}'$ 构成网络．当岛 $A$ 与 $C\in\mathscr{B}$ 之间的航线被关闭后，这种关系不再成立．
因此，这种情况最终一定会发生，此时，岛 $B$ 将同其他所有岛之间均有航线
【解析】
略
答案
解析
备注
