Задача М756‍‍

Если закрыть все авиалинии, ведущие из столицы, то остальные города разобьются на несколько зон, так что из любого города любой зоны можно перелететь в любой другой город этой зоны (не пользуясь закрытыми линиями) и нельзя перелететь в города других зон. В каждую зону обязательно ведёт хотя бы одна линия из столицы; докажем, что таких линий не менее двух.

Предположим, что это неверно, и в какую-то зону ведёт только одна авиалиния из столицы. Пусть $k$‍‍ — число городов в этой зоне, а $l$‍‍ — общее число соединяющих их авиалиний. Условимся считать, что на каждой линии $AB$‍‍ ежедневно совершаются 2 рейса — из $A$‍‍ в $B$‍‍ и обратно. Тогда число рейсов между городами зоны, совершаемых ежедневно, равно $2l$‍.‍ С другой стороны, число всех рейсов, следующих из городов зоны, равно $10k$‍,‍ причём только один из них заканчивается вне зоны — в столице. Поэтому $2l=10k-1$‍,‍ что, очевидно, невозможно.

Итак, в каждую зону ведёт не меньше чем 2 авиалинии из столицы. Откроем часть этих линий — по одной на зону, тогда по меньшей мере столько же, т. е. не менее $100:2=50$‍,‍ авиалиний останутся закрытыми. В то же время авиасообщение между любыми двумя городами страны, очевидно, восстановится.