Maths Olympiad Prep

Library / /359 of 397

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Taiwan

There are nn islands, where n3n \ge 3. 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 XX and YY that are connected by a route, and close the route between them. At the same time, for all other islands AA, if AA has a route to XX but not to YY, then the company will add a route between AA and YY; conversely, if AA has a route to YY but not to XX, then the company will add a route between AA and XX.
For two groups of islands AA and BB, if AAA \in A and BBB \in B, then we say the route connecting AA and BB links AA and BB. 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 A\mathcal{A} and B\mathcal{B} form a network if and only if for any AAA \in \mathcal{A} and BBB \in \mathcal{B}, there is a route between AA and BB.

1. First choose any route, and let its endpoints be islands AA and BB. Since n3n \ge 3, there must exist a third island CC; and by the assumption of the problem, it must be connected to AA or BB, so without loss of generality assume it is connected to AA. Define A0={A}\mathcal{A}_0 = \{A\}, B0={B,C}\mathcal{B}_0 = \{B, C\}; it is easy to see that (A0,B0)(\mathcal{A}_0, \mathcal{B}_0) forms a network. Note that A0B0=3|\mathcal{A}_0 \cup \mathcal{B}_0| = 3.

2. Next we prove that: if A0B03|\mathcal{A}_0 \cup \mathcal{B}_0| \ge 3, then in every year, we can always redivide A0B0\mathcal{A}_0 \cup \mathcal{B}_0 into two nonempty groups of islands A1\mathcal{A}_1 and B1\mathcal{B}_1, such that (A1,B1)(\mathcal{A}_1, \mathcal{B}_1) forms a network.
If the route closed by the company does not link A0\mathcal{A}_0 and B0\mathcal{B}_0, then we may simply keep the original grouping. Now suppose the company has closed some route linking AAA \in \mathcal{A} and BBB \in \mathcal{B}. Let us consider A1={A,B}\mathcal{A}_1 = \{A, B\} and B1=(A0B0){A,B}\mathcal{B}_1 = (\mathcal{A}_0 \cup \mathcal{B}_0) - \{A, B\}; it is easy to see that A0B0=A1B1\mathcal{A}_0 \cup \mathcal{B}_0 = \mathcal{A}_1 \cup \mathcal{B}_1, and both A1\mathcal{A}_1 and B1\mathcal{B}_1 are nonempty (since A0B03|\mathcal{A}_0 \cup \mathcal{B}_0| \ge 3).

Below we show that (A1,B1)(\mathcal{A}_1, \mathcal{B}_1) forms a network. Consider CA0{A}C \in \mathcal{A}_0 - \{A\}; since (A0,B0)(\mathcal{A}_0, \mathcal{B}_0) forms a network, there must be a route between CC and BB. If there was originally no route between CC and AA,

then when AB\overline{AB} is closed at the end of the year, AC\overline{AC} must be established. In other words, CC must have a connection to both AA and BB. Similarly, for all CB0{B}C \in B_0 - \{B\}, CC must have a connection to both AA and BB. This means that any island in B1B_1 has a connection to both AA and BB, so (A1,B1)(A_1, B_1) forms a network. This completes the proof.

3. Suppose A1B1<n|A_1 \cup B_1| < n. We now prove that: after some number of years, we can find an island CC not in A1B1A_1 \cup B_1, and redivide A1B1{C}A_1 \cup B_1 \cup \{C\} into two nonempty groups of islands A2A_2 and B2B_2, such that (A2,B2)(A_2, B_2) forms a network.
Let DA1B1D \notin A_1 \cup B_1. By the assumption of the problem, after some number of years, the company must close the route between DD and some island in A1B1A_1 \cup B_1, without loss of generality say it is AA1A \in A_1. Note that (A1,B1)(A_1, B_1) forms a network, so all points in B1B_1 have a route to AA; therefore, when AD\overline{AD} is closed, all points in B1B_1 will have a route to DD. Therefore, consider A2=A1{D}A_2 = A_1 \cup \{D\}, B2=B1B_2 = B_1, then (A2,B2)(A_2, B_2) forms a network and A2B2=A1B1{D}A_2 \cup B_2 = A_1 \cup B_1 \cup \{D\}. This completes the proof.

4. By 3., we may assume that after some number of years, we can divide all nn islands into two nonempty groups of islands AA and BB, such that (A,B)(A, B) forms a network. Now suppose that after some number of years, the route between AAA \in A and BBB \in B is closed. Let A={A,B}A' = \{A, B\}, and let BB' be all the other islands, then it is easy to see that (A,B)(A', B') forms a network.

Suppose that after some further number of years, without loss of generality, the route between AA and some BBB' \in B' is closed. Since BB has a route to all islands in BB', this means that when AB\overline{AB'} is closed, AB\overline{AB} will be established, that is, BB has a route to every other island. This completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.