Задача
№ 14290
Оценка + пример (экстремальные комбинаторные задачи)
Ур. 7
Всероссийская олимпиада школьников по математике, 10 класс, заключительный этап, 2021, задача 3
В стране $N$ городов. Некоторые пары городов связаны двусторонними авиалиниями, каждая пара не более, чем одной. Каждая авиалиния принадлежит одной из $k$ компаний. Оказалось, что из любого города можно попасть в любой другой (возможно, с пересадками), но при закрытии всех авиалиний любой из компаний это свойство нарушается. Какое наибольшее количество авиалиний (при произвольных данных $N$ и $k$) могло быть в этой стране?
Ответ:
Решение: