СПбГУ 2024, 10-11 классы, задача 5
( баллов) В стране городов. Некоторые из них соединены беспосадочными двухсторонними авиалиниями. Известно, что среди любых городов есть хотя бы пар городов, соединенных друг с другом авиалинией. Какое наименьшее возможное количество авиалиний может быть в этой стране.
Ответ: .
Решение. Разобьем городов на групп по городов в каждой и любые два города в каждой группе соединим авиалинией. Тогда в каждой группе по авиалиний и общее количество авиалиний . Покажем, что эти города удовлетворяют условию задачи. Действительно, рассмотрим какие-то городов. Пусть из них из первой группы, из второй, ..., из -й группы. Тогда общее количество авиалиний между этими городами равно
Поскольку неравенство справедливо для всех ,
Стало быть, .
Докажем теперь, что общее количество авиалиний всегда не меньше, чем . Разобьем города на две одинаковые по размеру группы и таким образом, что авиалиний между городами из наименьшее возможное количество. Рассмотрим пару городов и . Пусть город соединен авиалиниями с городами из , а город соединен авиалиниями с городами из . Тогда , поскольку в противном случае можно было бы поменять местами города и , уменьшив количество авиалиний между городами из .
Если каждый город из соединен авиалинией хотя бы с тремя городами из , то общее количество авиалиний будет не меньше чем (хотя бы авиалиний между городами из , хотя бы авиалиний ведет из в и хотя бы авиалиний между городами из ). В этом случае нужное неравенство доказано.
Если же найдется город из , соединенный авиалиниями не более чем с двумя городами из , то для любого города из есть не больше двух авиалиний ведущих в города из . Но тогда общее количество авиалиний между городами из не больше . Но по условию оно не меньше, чем , поэтому для любого города из есть ровно две авиалинии ведущие в города из . Пусть - один из городов, с которыми соединен город . Рассмотрим набор из городов: город и все города из , за исключением . Посчитаем общее количество авиалиний между городами этого набора. Между выбранными городами из в точности авиалинии (две авиалинии ведут в город ) и еще одна авиалиния ведет в город (вторая авиалиния из ведет в ), итого получилось авиалинии, что противоречит условию. Таким образом, этот случай невозможен.