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

задан 2 Янв '14 21:19

10|600 символов нужно символов осталось
2

Положим $%n=5000$%. Тогда из $%2n$% человек формируется $%2n(2n-1)/2=n(2n-1)=2n^2-n$% различных пар. Когда каждый из $%2n$% человек приглашает к себе в друзья $%n$% человек, то при этом оказывается задействовано $%2n^2$% пар (с повторениями). Из них как минимум $%n$% пар должно быть использовано дважды ввиду равенства $%2n^2-(2n^2-n)=n$%. Это значит, что $%n$% дружб гарантировано. Приведём теперь пример, показывающий, что возможно именно такое количество -- тем самым оно и будет наименьшим.

Рассмотрим правильный $%2n$%-угольник, и для любого соединения его вершин (то есть стороны или диагонали), которое не соединяет противоположные вершины, выберем направление определённым образом. А именно, если речь о соединении $%A$% и $%B$%, то среди двух дуг с концами $%A$%, $%B$% выбираем более короткую. При движении по часовой стрелке от начала такой дуги к её концу рисуем "стрелочку". Если она идёт от $%A$% к $%B$%, то это будет означать, что $%A$% добавил $%B$% в друзья. Легко видеть, что каждый добавит в друзья $%n-1$% человека в рамках описанной схемы. А для всех "длинных" соединений, то есть для пар противоположных вершин, добавления в друзья сделаем взаимными. Тогда каждый добавил ровно $%n$% друзей, и взаимных дружб установится в точности $%n$%.

ссылка

отвечен 2 Янв '14 22:32

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,699

задан
2 Янв '14 21:19

показан
781 раз

обновлен
2 Янв '14 22:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru