Решите задачу (7 баллов). В новой социальной сети зарегистрировалось 2000 человек

В новой социальной сети зарегистрировалось 2000 человек. Каждый из них пригласил к себе в друзья по 1000 человек. Два человека объявляются друзьями, только если каждый из них пригласил другого в друзья. Какое наименьшее количество пар друзей могло образоваться?

Решение. Положим n=1000. Всего возможных пар друзей Представим себе, что для каждой из m возможных паримеется свой ящик и что участник сети, делая приглашение дружить, кладёт в этот ящик шарик. Всего в ящики будет положено шариков (потому что у каждого из 2n участников по n шариков). Поскольку, шариков на n больше, чем ящиков, хотя бы в n ящиков попадёт по два шарика – значит, образуется не менее n пар друзей.

Покажем, что ровно n пар может образоваться. Представим, что 2n человек стоят по кругу (равномерно), и каждый приглашает в друзья n человек, следующих за ним по часовой стрелке. Тогда друзьями окажутся только те, кто стоит строго напротив друг друга.

Ответ: 1000

Оценивание. За верное решение – 7 баллов;

за доказательство того, что пар друзей 1000 – 4 балла;

за приведенный пример – 3 балла.