Skip to content / Đến nội dung
ThichHocToan.com

MathNet 2022-part-05 — 197 problems (EN–VI) Question 73

Math Olympiad Vault · MathNet 2022-part-05 — 197 problems (EN–VI)

Question 73

Let $N$ and $s$ be positive integers with $N \gt s$. In the Taipower park there are several buildings; exactly $N$ of them are power plants, and one more building is the headquarters. Between some pairs of buildings there are wires that can transmit power in one direction only, such that:

(i) every wire connected to a power plant only sends power out of the plant;

(ii) for every building other than the headquarters, there is a unique sequence of wires forming a route from that building to the headquarters.

A building is called $s$-level powered if and only if, after removing any one wire in the park, the building can still receive power from at least $s$ power plants. Find the largest possible number of $s$-level powered buildings.