Question

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

Answer 1

По моим расчетам 20 пар.

Answer 2

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

Для решения этой задачи, мы можем использовать принцип Дирихле, который утверждает, что если n + 1 объектов распределены по n ящикам, то хотя бы в одном из ящиков будет не менее двух объектов.

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

Таким образом, наименьшее количество пар друзей, которое могло образоваться, равно 1.

Источники: -: Ссылка на источник -: Ссылка на источник -: Ссылка на источник -: Ссылка на источник -: Ссылка на источник -: Ссылка на источник -: Ссылка на источник -: Ссылка на источник -: Ссылка на источник -: Ссылка на источник