Задача
№ 14258
Оценка + пример (экстремальные комбинаторные задачи)
Ур. 6
Всероссийская олимпиада школьников по математике, 10 класс, заключительный этап, 2026, задача 6
В стране ровно 1000 городов, некоторые пары городов соединены двусторонними авиалиниями. Известно, что для любого натурального $k\leqslant500$ выполнено следующее утверждение: «Если выбрать любое множество $A$ из $k$ городов, то найдётся хотя бы $k$ городов, не принадлежащих $A$, каждый из которых соединён авиалинией хотя бы с одним городом из $A$». Какое наименьшее количество авиалиний может быть в этой стране?
Ответ:
Решение: