Олимпиадная задача Александра Эвнина: минимальное число пар друзей на сайте, сложности 3 из 5
Задача
На новом сайте зарегистрировалось 2000 человек. Каждый пригласил к себе в друзья по 1000 человек. Два человека объявляются друзьями тогда и только тогда, когда каждый из них пригласил другого в друзья. Какое наименьшее количество пар друзей могло образоваться?
Решение
Оценка. Всего было отправлено 2000000 приглашений, а пар на сайте 1000·1999 = 1999000. Приглашений на 1000 больше, чем пар, поэтому внутри хотя бы 1000 пар было отправлено два приглашения. Значит, образовалось хотя бы 1000 пар.
Пример: расставим всех в вершинах правильного 2000-угольника, и пусть каждый пригласит 1000 следующих за ним по часовой стрелке. Тогда друзьями окажутся только те, кто расположен в противоположных вершинах.
Ответ
1000 пар.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь