Юниорская олимпиада по математике. Заключительный этап. 2022-2023 учебный год. 8 класс.

В стране 2023 городов и $n$ дорог. Каждая дорога соединяет некоторые пары различных городов и между любыми двумя городами не более одной дороги. Известно, что по этим дорогам можно добраться из любого города в любой другой. Поскольку содержание этих дорог стало дорогостоящим, правительство решило закрыть строго больше $80\%$ из них так, чтобы из любого города можно было попасть в любой другой город по оставшимся дорогам. Это решение понравилось жителям страны и им было предложено выбрать 2 дороги, которые правительство не закроет. Найдите наименьшее возможное значение $n$, что при любом изначальном расположений дорог и при любом выборе жителей правительство сможет выполнить свой план.

Комментарий/решение

Переведем задачу в графы. Так как граф после удаления некоторых ребер должен остаться связным , граф в конце содержит как минимум $n-1(n=2023)$ ребер,соответственно изначальный граф содержит хотя бы $5(n-1)+1$ ребер теперь покажем что этого достаточно.

В графе выделим остовное дерево и в идеале мы должны убрать все ребра не входящие в это остовное дерево, пусть жители решили оставить одно такое ребро,пусть это $AB$ и по определению существет путь от $А$ до $В$ отличный от самого ребра $АВ$ тем самым эти вершины лежат на каком то замкнутом цикле значит если мы уберём вместо $АВ$ другое ребро тоже лежащее на том же цикле то связность сохраняется,а мы можем так сделать потому что в цикле хотя бы $3$ ребра а жители в праве оставить максимум $2$ из них.И доказательство на этом завершается,ответ $10111$