MathDB
Bombing the Tree!

Source: 2024 IMOC C4 (Night 6)

August 8, 2024
combinatoricsgraphtree

Problem Statement

The REAL country has nn islands, and there are n1n-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 nn 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 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 nn and the layout of the bridge, the method of bombing the islands is the only one. Proposed by chengbilly