Задача
COM-B1-M04-P021 Много знакомств
#21
★★★★☆ Уровень 4 из 5
В группе \(15\) человек каждый знаком не менее чем с \(7\) другими. Докажите, что всего есть не менее \(53\) пар знакомых.
Сложите степени в графе знакомств.
Построим граф знакомств. Сумма степеней не меньше \(15\cdot7=105\). Каждая пара знакомых даёт два вклада в сумму степеней, значит число рёбер не меньше \(105/2=52.5\). Так как оно целое, оно не меньше \(53\).
Оценка через двойной подсчёт и округление.