In a certain country there are $2023$ islands and $2022$ bridges, such that every bridge connects two different islands and any two islands have at most one bridge in common, and from any island, using bridges one can get to any other island. If in any three islands there is an island with bridges connected to each of the other two islands, call these three islands an "island group". We know that any two "island group"s have at least $1$ common island. What is the minimum number of islands with only $1$ bridge connected to it?
Problem
Source: 2023 China Western Mathematical Olympiad Grade p2 CWMI
Tags: combinatorics
06.04.2024 09:15
Looks like the answer is 1011. I'll work out the details, and post the proof (if I'm able to)
07.04.2024 03:47
Call an island 'lonely' if only 1 bridge is connected to it. Call two islands are 'direcly connected' if there is a bridge between them. We can easily find out that there are at least $2$ lonely islands(since the islands form a tree). Suppose $A_1$ and $A_2$ are two lonely islands. Case 1 $A_1$ and $A_2$ are both connected to an island $B$ Then $A_1,A_2,X$ forms an island group, which means every island group has to include $X$. So starting from $X$, one can get to any island using at most two bridges. That makes the number of lonely islands at least $2+(2023-3)/2=1012$ Case 2 $A_1$ is directly connected to an island $B_1$ and $A_2$ is directly connected to an island $B_2$. Since the islands are connected, $B_1$ and $B_2$ are not lonely. If $B_1$ and $B_2$ are directly connected, as they are also connected to other islands WLOG, suppose $C$ is directly connected to $B_1$, which is different form $A_1,B_2$ No other islands is directly connected to $B_2$ then(otherwise we have two island groups $C,B_1,A_1$ and $D,B_2,A_2$) So in order to have a common island with the island group$B_1,B_2,A_2$, every island group has to contain $B_1$ Similarly to case 1, we have at least $1012$ lonely islands. If $B_1$ and $B_2$ are not directly connected Suppose $B_1$ is directly connected to an island $C_1$ and $B_2$ is directly connected to an island $C_2$. We have two island groups $C_1,B_1,A_1$ and $C_2,B_2,A_2$, they should have 1 common island. So $C_1$ and $C_2$ have to be the same island, we renote them as $C$. That is to say, excluding $A_1$ and $A_2$, $B_1$ and $B_2$ are directly connected to and only directly connected to island $C$ Then every island group has to contain$C$. Therefore we have at least $(2023-1)/2=1011$ lonely islands. In conclusion, there are at least $1011$ lonely islands, the following shows an example. Call the islands $X,Y_1,Y_2,...Y_{1011},Z_1,Z_2,...,Z_{1011}$ Build a bridge between $X$ and $Y_i$, $i=1,2,...,1011$, respectively. Then build a bridge between $Y_i$ and $Z_i$, $i=1,2,...,1011$, respectively. These bridges follows the rules and only the $Z$s are lonely.