Комбинаторная задача

[mr.tumkan2015]

На сайте Druzhby.net зарегистрировалось 5000 человек. Каждый пригласил к себе в друзья по 2500 человек. Дружба между двумя людьми случается тогда и только тогда, когда каждый из них пригласил другого в друзья. Какое наименьшее количество дружб могло случиться?

Я проверил, что если рассмотреть 4 человека, то дружб будет $2$ минимум, для шести будет три. Может все-таки ответ $2500$. По индукции не получилось, запутался в обилии вариантов.

1) $5000\cdot 2500=12500000$ (Человек зарегестрировались всего)

2) $12500000-5000=12495000$ (Дружб)

Правильно ли это?

Я проверил, что если рассмотреть 4 человека, то дружб будет $2$ минимум, для шести будет три. Может все-таки ответ $2500$. По индукции не получилось, запутался в обилии вариантов.

[provincialka]

mr.tumkan2015 в сообщении #1063989 писал(а):

1) $5000\cdot 2500=12500000$ (Человек зарегестрировались всего)

Нет, зарегистрировалось только 5000 человек.

mr.tumkan2015 в сообщении #1063989 писал(а):

2) $12500000-5000=12495000$ (Дружб)

То есть? Что из чего вы вычитаете?

[Mihaylo]

mr.tumkan2015 в сообщении #1063989 писал(а):

1) $5000\cdot 2500=12500000$ (Человек зарегестрировались всего)

Не человек, а количество односторонних дружб. Нужно же пересчитать двухсторонние (взаимные) дружбы. Это количество зависит от стратегии выбора друзей. Есть некоторая оптимальная стратегия, при которой количество взаимных дружб наименьшее. И еще: принцип Дирихле.

[alhimikoff]

Как-то так, может быть не очень строго. Надо ещё построить стратегию заключения дружбы.

Всего приглашений
$5000\cdot 2500=12500000$
Значит кому-то обязательно придёт $2500$ или больше приглашений.

Пусть человеку A пришло ровно $2500$ приглашений. Тогда есть лишь $2499$ человек, которые не отправляли приглашение человеку A, и он обязан заключить одну дружбу.
Если всем пришло по $2500$ приглашений, то минимальное число дружб $2500$.

Если имеет место неравномерное распределение приглашений:

Пусть человеку A пришло $2500+k$ приглашений. Он обязан дружить с $k+1$ человек. Эти лишние $k$ приглашений как-то распределились по $m\leqslant k$ человек, которые получили меньше $2500$ приглашений и не обязаны дружить. Минимальное число дружб : $k+1+2500-(m+1)$

То есть неравномерное распределение приглашений может только увеличить число дружб, ответ - $2500$.

[Lia]

alhimikoff
Замечание за полное решение учебной задачи.