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

Мемлекетте 2023 қала және $n$ жол бар. Әрбір жол әртүрлі екі қаланы байланыстырады және кез келген екі қала арасында бір жолдан аспайды. Осы жолдармен кез келген қаладан кез келген басқа қалаға жетуге болатыны белгілі. Бұл жолдарды күтіп ұстау қымбатқа түскендіктен, кез келген қаладан қалған жолдармен кез келген басқа қалаға жетуге болатындай, үкімет жолдардың $80\%$-дан қатаң астамын жабу туралы шешім қабылдады. Бұл шешім ел тұрғындарына ұнады және оларға үкімет жаппайтын 2 жолды таңдау ұсынылды. Жолдардың кез келген бастапқы орналасуымен және тұрғындардың кез келген таңдауымен үкімет өз жоспарын орындай алатындай $n$-нің ең кіші мүмкін мәнін табыңыз.

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

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

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