Все 30 городов некоторого государства соединены прямыми авиалиниями. Правительство решило сократить число авиалиний. Какое наибольшее их количество можно закрыть, чтобы можно было по-прежнему долететь из любого города в любой другой, но, возможно, с пересадками?

Для того чтобы выяснить, сколько авиалиний можно закрыть, сохраняя возможность добраться из любого города в любой другой с пересадками, необходимо рассмотреть структуру, в которой соединены города.

30 городов соединены авиалиниями, что можно представить как граф, где города — это вершины, а авиалинии — ребра. Чтобы гарантировать возможность добраться из любого города в любой другой (возможно, с пересадками), необходимо сохранить связность графа.

Для связного графа с \( n \) вершинами, минимально возможное количество рёбер (или авиалиний) — это \( n - 1 \). В нашем случае \( n = 30 \), соответственно, минимальное количество рёбер, необходимое для связности, равно \( 30 - 1 = 29 \).

Таким образом, максимальное количество авиалиний, которые могут быть закрыты, равно:

\[ \text{Количество закрытых авиалиний} = \text{Общее количество авиалиний} - \text{Минимально необходимое количество авиалиний} = \binom{30}{2} - 29 \]

Общее количество авиалиний (ребер) между 30 городами можно вычислить по формуле комбинаторики:

\[ \binom{30}{2} = \frac{30 \times 29}{2} = 435 \]

Итак, максимальное количество авиалиний, которые можно закрыть, составит:

\[ 435 - 29 = 406 \]

Таким образом, наибольшее количество авиалиний, которое можно закрыть, сохраняя возможность добраться из любого города в любой другой, равно 406.