MathDB
Problems
Contests
National and Regional Contests
Taiwan Contests
IMOC Shortlist
2024-IMOC
C4
C4
Part of
2024-IMOC
Problems
(1)
Bombing the Tree!
Source: 2024 IMOC C4 (Night 6)
8/8/2024
The REAL country has
n
n
n
islands, and there are
n
−
1
n-1
n
−
1
two-way bridges connecting these islands. Any two islands can be reached through a series of bridges. Arctan, the king of the REAL country, found that it is too difficult to manage
n
n
n
islands, so he wants to bomb some islands and their connecting bridges to divide the country into multiple small areas. Arctan wants the number of connected islands in each group is less than
δ
n
\delta n
δ
n
after bombing these islands, and the island he bomb must be a connected area. Besides, Arctan wants the number of islands to be bombed to be as less as possible. Find all real numbers
δ
\delta
δ
so that for any positive integer
n
n
n
and the layout of the bridge, the method of bombing the islands is the only one. Proposed by chengbilly
combinatorics
graph
tree